【leetcode】Find Minimum in Rotated Sorted Array I&&II

题目概述：

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

解题思路：

在一个有顺序的数组中查找个最小值，很容易想到的就是二分法，的确，这里用的就是二分，不过要做一点改进。
改进的思路是这样的：
1.我们容易想到最好的情况就是这个数组是普通的排好序的，如【1,2,3,4】，那么最小的必然是下标最小的。用旋转的情况假设第一个小于最后一个那么最小值肯定也是第一个，也就是说计算过程中只要找到left<right的结果就出来了 2、如果这里面出现了rotate的话，如【3,4,1,2】那么最小值肯定会出现在左右的一遍，那么到底是哪边呢，这里我们可以比较最左和最后值的大小，比如这里`3="">2说明在这里前面的那个3是旋转过去的。这是后我们就要用中间那个值，这里是(0+3)/2=1`这里4>2(right)说明最小值应该实在后半块里的，于是乎改left就好。反之是改right就是一样的过程了，就是一个二分的思想

 1 class Solution:
 2     # @param num, a list of integer
 3     # @return an integer
 4     def findMin(self, num):
 5         l = len(num)
 6         left = 0
 7         right = l-1
 8         while num[left] > num[right]:
 9             mid = (left +right)/2
10             if num[mid] < num[right]:
11                 right = mid
12             else :
13                 left = mid + 1
14         return num[left]
15 
16 a = [3,0,1,2]        
17 #a = [4, 5, 6, 7, 8, 9, 18,19, 0, 1, 2, 3]
18 s = Solution()
19 print s.findMin(a)
20

加深问题：Find Minimum in Rotated Sorted Array II

题目描述：

跟上面的一样，唯一改变的是现在数字可以重复了

解题思路：

这个看起来改了一点，实际上直接用上面的方法就很难得出结果里，leetcode给这个的评级是hard，但是我开始实在是想不出有什么好办法，后来发现解法是：对于相等的存在无法判断只能暴力-_-#。不过我的代码有点丑陋，直接上一题加的，改了个特殊情况，leetcode的标程比这个好看些，不过效率差不多。

 1 class Solution:
 2     # @param num, a list of integer
 3     # @return an integer
 4     def findMin(self, num):
 5         l = len(num)
 6         left = 0
 7         right = l-1
 8         while num[left] >= num[right]:
 9             mid = (left +right)/2
10             if num[mid] < num[right]:
11                 right = mid
12             elif num[left] > num[right]:
13                 left = mid + 1
14             else :
15                 if right == left:
16                     return num[left]
17                 res = 10000
18                 for i in xrange(0,l):
19                     if num[i] < res:
20                         res = num[i]
21                 return res
22         return num[left]
23 
24 a = [2,0,1,1,1]        
25 #a = [3,4, 5, 6, 7, 8, 9, 18,19, 0, 1, 2, 3]
26 s = Solution()
27 print s.findMin(a)
28