1. 154

find-minimum-in-rotated-sorted-array-ii

2. 算法

• O(lgn)

• 最差情况：O(n)：全部都一样

3. 代码

class Solution {

public:

    int findMin(vector<int>& nums) {

        int left=0,right=nums.size()-1;

        int mid, ans=nums[0];

        while(left<right){

            mid=(left+right)/2;

            if(nums[left]<nums[mid]){

                ans=min(ans,nums[left]);

                left=mid+1;

            }else if(nums[right]>nums[mid]){

                ans=min(ans,nums[mid]);

                right=mid;

            }else{

                ans=min(ans,nums[left]);

                ++left;

            }

        }

        return ans;

    }

};