首页 > 代码库 > Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/
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.
解题思路：
最朴素的O(n)的方法，就是找到突然变小的那个元素，肯定是最小的。否则就说明所有元素一直变大，本来就是排序的，则返回第一个元素。
public class Solution { public int findMin(int[] num) { if(num.length == 0){ return 0; } int min = num[0]; for(int i = 0; i < num.length; i++){ if(num[i] < min){ return num[i]; } } return min; }}
不过本题还有一个二分查找的方法，可以将时间复杂度降为O(lgN)。代码如下。
public class Solution { public int findMin(int[] num) { if(num.length == 0){ return 0; } if(num.length == 1){ return num[0]; } int start = 0; int end = num.length - 1; int min = Integer.MAX_VALUE; if(num[start] < num[end]){ return num[start]; } while(start <= end){ if(start == end){ return Math.min(min, num[start]); } int mid = (start + end) / 2; if(num[start] <= num[mid]){ min = Math.min(min, num[start]); start = mid + 1; }else{ min = Math.min(min, num[mid]); end = mid - 1; } } return min; }}
二分查找是一个很简单，却很难完全写对的算法，编程珠玑里写道，差不多只有10%的程序员能正确的实现它。问题主要处在边界变量的定义，和循环条件的定义上。让我们从程序的开头看起。
将end定义为length - 1，就意味着这是一个[0, length - 1]的左右都闭合的区间，所以循环的条件一定是start <= end。所以再到循环内部，start = mid + 1, end = mid - 1，都是因为这是一个闭合的区间，这样做才不会漏元素。
如果end定义为length，那么就意味着这个区间是左闭合有开的，[0, length)。所以后面while的条件就变为start < end，循环内部，start = mid + 1, end = mid。
这样理解起来就不会出错。其实这就是循环不变式的概念，invariant。可以参考下面的页面，对于这个比较基础的知识介绍的很好。
http://www.cppblog.com/converse/archive/2009/09/21/96893.aspx
Find Minimum in Rotated Sorted Array