【数组】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.

思路:

这题其实就是找翻转后右侧部分的最左端点,典型的二分搜索变体,大致思路分成两种情况讨论:

1.如果中间点在翻转后的左侧,则应该往右寻找,因为如果没有冗余元素,最小值不可能出现在左侧;

2.如果中间点在翻转后的右侧,则应该往左寻找。不过这时应该保存下当前中间点对应的元素,它有可能是最小的。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    var l=0,r=nums.length-1,mid,temp=-2147483648;
    
    while(l<=r){
        mid=l+Math.floor((r-l)/2);
        
        if(nums[l]<=nums[r]){
            return nums[l];
        }else{
            if(nums[l]>nums[mid]){//翻转点在mid左侧
                r=mid;
            }else{//反转点在mid右侧
                l=mid+1;
            }
        }
    }
};
原文地址:https://www.cnblogs.com/shytong/p/5131969.html