154. Find Minimum in Rotated Sorted Array II(循环数组查找)

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.

The array may contain duplicates.

Example 1:

Input: [1,3,5]

Output: 1

Example 2:

Input: [2,2,2,0,1]

Output: 0

class Solution {

public:

    int findMin(vector<int>& nums) {

        int len=nums.size();

        if(len==1) return nums[0];

        int low=0,high=len-1;  //有重复的数字从mid 和high 比较来辨别 寻找的位于左半部分还是右半部分，没有的话用 mid和low位置比较划分

        while(low<=high){

            int mid=low+(high-low)/2;

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

                high=mid;

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

                low=mid+1;

            }else{

            high--;

            }

        }

        return nums[low];

    }

};

巴特西

154. Find Minimum in Rotated Sorted Array II(循环数组查找)

最新文章

热门文章