153. Find Minimum in Rotated Sorted Array

problem description

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.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

algorithm thought

这题和之前find target in rotated array那题很像。这里是找到最小值。首先，如果一个数组是有序的，那么最小值肯定就是第一个数，如果在哪个地发rotate了，那么那个点就是最小值，也是我们需要找的值。

这里一样可以用二分查找解决，首先我们判断数组首是否小于尾，如果小于那就是有序的，直接返回数组首值。否则，找到mid，判断mid和首元素的关系，如果是顺序的，那么我们下一个找的应该是右数组，如果不是有序的，那么就在左数组中找到那个rotate点

code

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-left)/2;
            if(nums[mid]>=nums[left])
                left=mid+1;
            else
                right=mid;
        }
        return nums[left];
    }
};

algorithm analysis

利用二分查找解决问题，时间复杂度O(lgn)