1class Solution(object):
2 def findMin(self, nums):
3 """
4 :type nums: List[int]
5 :rtype: int
6 """
7 if not nums:
8 return None
9 return self.__fmin(nums, 0, len(nums) - 1)
10
11 def __fmin(self, nums, i, j):
12 if i == j:
13 return nums[i]
14 if i + 1 == j:
15 return min(nums[i], nums[j])
16 if nums[i] < nums[j]:
17 return nums[i]
18 mid = int((i + j) / 2)
19 if nums[i] < nums[mid]:
20 return self.__fmin(nums, mid, j)
21 return self.__fmin(nums, i, mid)
22
23
24class Solution2(object):
25 def findMin(self, nums):
26 """
27 :type nums: List[int]
28 :rtype: int
29 """
30 if not nums:
31 return None
32 lo = 0
33 hi = len(nums) - 1
34 while lo < hi:
35 mid = (lo + hi) / 2
36 if (nums[mid] > nums[hi]):
37 lo = mid + 1
38 else:
39 hi = mid
40 return nums[lo]
41
42
43in_arrs = [
44 [3, 4, 5, 1, 2],
45 [4, 5, 6, 7, 0, 1, 2],
46 [8, 1, 2, 3],
47 [1, 2, 3, 4],
48 [1],
49 [],
50 None,
51]
52
53exp_out = [
54 1,
55 0,
56 1,
57 1,
58 1,
59 None,
60 None,
61]
62
63if __name__ == "__main__":
64
65 sol = Solution()
66 sol2 = Solution()
67 for idx, nin in enumerate(in_arrs):
68 r = sol.findMin(nin)
69 print(exp_out[idx] == r, r)
70 r = sol2.findMin(nin)
71 print(exp_out[idx] == r, r)