154. Find Minimum in Rotated Sorted Array II

[blueWind123731]

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

Note: This is a follow up problem to Find Minimum in Rotated Sorted Array. Would allow duplicates affect the run-time complexity? How and why?

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

[blueWind123731]

二分查找：将数组看成两个非递减的子数组，所以最小值一定在第二个子数组的第一个，只要数组旋转了最小值就处于相对“右边”。即不断的比较中间值和“右侧值”就能找到最小值。

var findMin = function(nums) {
    let left = 0,right = nums.length-1
    while(left<right){
        let mid = parseInt((left+right)/2)
        if(nums[mid]<nums[right]){
            right = mid
        }else if(nums[mid]>nums[right]){
            left = mid+1
        }else {
             // 若相等，则最小的数一定在数组的靠左边，则right左移
            right--
        }
    }
    return nums[left]
};