153 - Find Minimum in Rotated Sorted Array

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.

Hide Tags

Array Binary Search

Hide Similar Problems

(H) Search in Rotated Sorted Array (H) Find Minimum in Rotated Sorted Array II

当然是二分查找，只是查找的判断方法变了一下，

如果同时小于last和next，则为正解，如果切分到start==end，也就是它；

如果小于end的值，那么最小值在左边，反之在右边。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int rst;
        find(nums, 0, nums.size()-1, rst);
        return rst;
    }
   
    void find(vector<int>& nums, int start, int end, int& min)
    {
        if(start>end)
            return;
        int mid = (start+end)/2;
        int last = (start<mid)?(mid-1):end;
        int next = (end>mid)?(mid+1):start;

        if((start==end)||(nums[mid]<nums[last]))  //不用判断是不是还大于next
            min = nums[mid];
        else if(nums[mid]<nums[end])
            find(nums, start, mid-1, min);
        else
            find(nums, mid+1, end, min);
        return;
    }
};