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.

二、思路

本题意是找到数组存在翻转的位置，如果不存在返回数组最左边的元素。分三种情况：

Case 1. 正常顺序，即没有反转，此时返回最左边的数。
[1 2 3 4 5 6 7 ]

Case 2. 中间元素大于最左和最右元素T。
 [ 4 5 6 7 0 1 2 3 ]

Case 3. 中间元素小于最左和最右元素。
e.g> [ 5 6 7 0 1 2 3 4 ]

三、代码

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