limanting 的个人博客

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function (numbers) {
    var left = 0;
    var right = numbers.length - 1;
    while (left !== right) {
        if (numbers[left] > numbers[right]) {
            const p = parseInt((right + left) / 2);
            if (numbers[p] >= numbers[left]) {
                left = p + 1;
            } else {
                right = p;
            }
        } else if (numbers[left] === numbers[right]) {
            right--;
        } else {
            right = left;
        }
    }
    return numbers[left];
};

这里面加快计算速度的是二分法。能将复杂度降低为O(lg2~n)。

二分法的主要实现方法就是有左右两个指针，当指针相等时，就是找到目标值的时候。