刷题-旋转数组的最小数字

本文主要是介绍刷题-旋转数组的最小数字，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、题目要求

二、重点难点分析

　　1.首先它是一个升序排列的数组，并旋转了，以至于最小值右边都是小于numbers[right]，最小值的左边都是大于numbers[right]，所以当中间数小于numbers[right]时，说明此时的right并不是最小值，right要向左边靠，此时 右边界变为 right=mid；当中间数大于numbers[right]时，因为中间数的左边数大于右边的数，所以左边界要向右边靠拢，此时 left（左）=mid +1；

　　2.为什么这里可以用到二分？二分的条件是排序的数组，因为旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素都是大于或等于后面子数组的元素；而且我们可以注意到最小值其实是这两个子数组的分界线；分别设置两个指针，一个指向最左边（递增子数组）另一个指向最右边（最后一个）

　　3.如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面

　　4.我的理解：第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件

三、代码展示

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length - 1;
    while( left <= right){
        let mid = Math.floor((left+right)/2);
        if( numbers[mid] < numbers[right]){
            right = mid;
        }else if( numbers[mid] > numbers[right])
        {
            left = mid + 1;
        }else{
            right -=1;
        }
    }
    return numbers[left];
};

这篇关于刷题-旋转数组的最小数字的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！