153.Find Minimum in Rotated Sorted Array

153.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.

有一个排好序的数组，可能从中间某个元素开始有环形存在，假设不存在重复元素，请找出其中的最小值。

第一眼看到这道题的时候我直接对数组进行了遍历，然后维护一个min指针指向数组中的最小元素，AC之后看了一下时间只用了4ms，觉得时间性能还不错，代码如下:

/*solution1*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int size=nums.size();
        int i=0,min=0;
        for(i=0;i<size;i++){
            if(nums[i]<nums[min])
                min=i;
        }
        return nums[min];
    }
};

不过看了讨论区之后觉得自己的答案和大牛们比起来简直太小学生了，上面的算法时间复杂度为O(n)，而大牛们通过使用binary_search将时间复杂度降低到了O(lgN).下面我来简述一下binary search解决此题的思路。

因为是排好序的数组，所以只需要分为三种情况

1. [0,1,2,3,4,5,6,7]这种情况的特征是最左边的值小于最右边，所以最左边的一定是minimum，直接返回。
2. [4,5,6,7,0,1,2,3]这种情况的特征是中间的数大于最右边的数，所以minimum一定出现在右半区中，调整到右半区继续查找。
3. [5,6,7,0,1,2,3,4]这种情况的特征是中间的数小于最左边的数，所以minimum一定出现在左半区中，调整到右半区继续查找。 代码如下:

/*solution2*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int size=nums.size(),low=0,high=size-1,mid=0;
        while(low<high){
            if(nums[low]<nums[high])
                return nums[low];
            mid=(low+high)/2;
            if(nums[mid]>nums[high])
                low=mid+1;
            else
                high=mid;
        }
        return nums[low];
    }
};

代码AC之后，我查看了运行时间，还是4ms，时间上没有太大的改变，应该是和测试用例有关，但时间复杂度降低到了对数级，在数据量较大的时候应该就能显示出来差异了。