题目：

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.

 

代码：oj测试通过 Runtime: 52 ms

1 class Solution: 2     # @param num, a list of integer 3     # @return an integer 4     def findMin(self, num): 5         # none case 6         if num is None: 7             return None 8         # short lenght case 9         if len(num)==1 :10             return num[0]11         # binary search12         start = 013         end = len(num)-114         while start<=end :15             if start==end :16                 return num[start]17             if start+1==end :18                 return min(num[start],num[end])19             mid = (start+end)/220             if num[mid]>num[start] :21                 if num[mid]>num[end] :22                     start = mid23                 else:24                     return num[start]25             else:26                 if num[mid]>num[end] :27                     return num[end]28                 else:29                     end = mid

 

思路：

基本思路还是binary search。

注意修改start或end时的条件：因为mid也有可能是最小值，所以start=mid end=mid，这个跟传统二分查找时start=mid+1以及end=mid-1有所不同。

想明白这些后，代码一次AC。

 

 

 

【续】

自己的上一版代码还是太复杂的；复杂的原因是把binary search的常规套路生搬硬套，没有考虑这道题目要求的是最小值就可以了。

改进后的代码如下：

1 class Solution: 2     # @param num, a list of integer 3     # @return an integer 4     def findMin(self, num): 5         # none case 6         if num is None: 7             return None 8         # short length case 9         if len(num)==1 :10             return num[0]11         # binary search12         start = 013         end = len(num)-114         while start<=end and num[start]>num[end]:15             mid = (start+end)/216             if num[mid]>num[end]:17                 start = mid+118             else:19                 end = mid20         return num[start]

oj测试通过 Runtime: 57 ms

还是向别人的代码学习来的。

1. 如果是没有rotate的有序数组，那直接就返回最左边的元素就可以了

2. 如果有rotate的情况，情况稍微有些复杂。但是核心点只有一个：rotate前最左边的元素一定是最小的，当然也小于最右边的元素；但是rotate后，最左边的元素一定不是最小的了，而且最左边的元素一定大于最右边的元素。

搞清楚上面这个思路，问题就变得简单很多（很多if else之类的判断条件就可以省略了）

3. 之前自己写binary search总是爱把start==end（start跟end重叠了） start+1==end（只剩两个元素了）两种case单独拎出来，然后放心大胆地用mid=(start+end)/2再进行后面的判断。这种方法的好处是可以放心大胆，缺点就是代码有时候比较冗长。跟别人的代码学习后，可以用一个条件判断直接省略这两种special cases。

　　3.1 num[start]>start[end]就可以保证不出现start==end的情况；且一旦num[start]>num[end]了，就证明当前处理的数组已经逃离rotate的影响了（见2中的红字和蓝字部分），就可以直接返回num[start]了。

　　3.2 再考虑start+1==end的case: [2,1]这种情况，mid取start，则num[mid]>num[end]，start=mid+1=end，退出while循环，num[start]取到了最小值；如果是[1,2]，end=mid=start，同样num[start]取到了最小值。

考虑清楚上述的思路，新一版的简洁代码也就可以敲定了。