题解 | #旋转数组的最小数字#

此题二分查找中间值应该和哪个值比较？

• 此题旋转数组中的旋转点将数组分为两个有序部分，左有序部分的元素必然大于右有序部分的所有元素，且最小值在右有序部分。因此我们要将区间定位到右有序部分，并逐渐缩小区间找到最下值。
• 由于右有序部分的最大值为右边界值，因此可以用中间值和右边界值比较，如果中间值大于右边界值，说明此时中间值在左有序部分，需要改变left指向middle+1将其逐渐向右有序部分靠近。如果中间值小于右边界值，说明此时中间值在右有序部分，要让right变为middle缩小右有序部分的区间来寻找最小值。如果中间值等于右边界值，只能一点点缩小右边界来寻找最下值。

参考

https://blog.nowcoder.net/n/770b93c590f149af876b34dcf252c009?f=comment

https://blog.nowcoder.net/n/438b4913b64948ad931f7f2a422770c5?f=comment

function minNumberInRotateArray(rotateArray)
{
    // write code here
    let left = 0;
    let right = rotateArray.length-1;
    let middle;

    while (left < right) {
        middle = Math.floor((right+left)/2);

        if (rotateArray[middle] > rotateArray[right]) {  // 中间值大于右边界值，说明中间值在左排序数组中，最小的数字在右边，因为左边部分一定大于右边部分
            left = middle + 1;
        }
        else if (rotateArray[middle] === rotateArray[right]) {  // 两者相等，无法确定最小值，要缩小右界
            right--;
        }
        else {  // 中间值小于右边界值，说明中间值在右排序数组中，此时缩小右界范围
            right = middle;
        }
    }
    return rotateArray[left];
}
module.exports = {
    minNumberInRotateArray : minNumberInRotateArray
};