1class Solution(object):
2 def search(self, nums, target):
3 """
4 :type nums: List[int]
5 :type target: int
6 :rtype: int
7 """
8 if not nums:
9 return -1
10 return self.__search(nums, 0, len(nums) - 1, target)
11
12 def __binsearch(self, nums, i, j, target):
13 if i == j:
14 if nums[i] == target:
15 return i
16 return -1
17
18 if i + 1 == j:
19 if nums[i] == target:
20 return i
21 if nums[j] == target:
22 return j
23 return -1
24
25 mid = int((i + j) / 2)
26 if nums[mid] < target:
27 return self.__binsearch(nums, mid, j, target)
28 return self.__binsearch(nums, i, mid, target)
29
30 def __search(self, nums, i, j, target):
31 if i == j:
32 if nums[i] == target:
33 return i
34 return -1
35
36 if i + 1 == j:
37 if nums[i] == target:
38 return i
39 if nums[j] == target:
40 return j
41 return -1
42
43 if nums[i] < nums[j]:
44 return self.__binsearch(nums, i, j, target)
45
46 mid = int((i + j) / 2)
47 if nums[i] < nums[mid]:
48 if (target <= nums[mid]) and (target >= nums[i]):
49 return self.__binsearch(nums, i, mid, target)
50 return self.__search(nums, mid, j, target)
51 if (target >= nums[mid]) and (target <= nums[j]):
52 return self.__binsearch(nums, mid, j, target)
53 return self.__search(nums, i, mid, target)
54
55
56class Solution2(object):
57 def find_min_index(self, nums):
58 """
59 :type nums: List[int]
60 :rtype: int
61 """
62 if not nums:
63 return None
64 lo = 0
65 hi = len(nums) - 1
66 while lo < hi:
67 mid = (lo + hi) / 2
68 if (nums[mid] > nums[hi]):
69 lo = mid + 1
70 else:
71 hi = mid
72 return lo
73
74 def search(self, nums, target):
75 """
76 :type nums: List[int]
77 :type target: int
78 :rtype: int
79 """
80 if not nums:
81 return -1
82 rot_index = self.find_min_index(nums)
83 hi = len(nums) - 1
84 if rot_index == 0:
85 return self.__binsearch(nums, rot_index, hi, target)
86 if target >= nums[rot_index] and target <= nums[hi]:
87 return self.__binsearch(nums, rot_index, hi, target)
88 return self.__binsearch(nums, 0, rot_index - 1, target)
89
90 def __binsearch(self, nums, i, j, target):
91 if i > j:
92 return -1
93 if i == j:
94 if nums[i] == target:
95 return i
96 return -1
97
98 if i + 1 == j:
99 if nums[i] == target:
100 return i
101 if nums[j] == target:
102 return j
103 return -1
104
105 mid = int((i + j) / 2)
106 if nums[mid] < target:
107 return self.__binsearch(nums, mid, j, target)
108 return self.__binsearch(nums, i, mid, target)
109
110
111in_arrs = [
112 ([3, 4, 5, 1, 2], 4),
113 ([4, 5, 6, 7, 0, 1, 2], 1),
114 ([8, 1, 2, 3], 3),
115 ([1, 2, 3, 4], 5),
116 ([1], 1),
117 ([], 1),
118 (None, 1),
119 ([5, 1, 3, 4], 5),
120 ([8, 1, 2, 3], 1),
121 ([1, 2, 3, 4], 4),
122 ([1, 2, 3, 4], 1),
123 ([1], 0),
124]
125
126exp_out = [
127 1,
128 5,
129 3,
130 -1,
131 0,
132 -1,
133 -1,
134 0,
135 1,
136 3,
137 0,
138 -1,
139]
140
141if __name__ == "__main__":
142
143 sol = Solution()
144 sol2 = Solution()
145 for idx, nin in enumerate(in_arrs):
146 r = sol.search(nin[0], nin[1])
147 print(exp_out[idx] == r, r)
148 r = sol2.search(nin[0], nin[1])
149 print(exp_out[idx] == r, r)