Suppose an array sorted in ascending order 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        if (nums[0] <= nums[len-1]){
            return nums[0];
        }
        else{
            int low = 0;
            int high = len-1;
            int mid = (low + high) / 2;
            while(low < high){
                if(nums[mid] > nums[high]){
                    low = mid + 1;
                }
                else{
                    high = mid;
                }
                mid = (low + high) / 2;
            }
            return nums[mid];
        }
    }
};