剑指Offer-11-旋转数组的最小数字

难度：简单

Description

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3, 4, 5, 1, 2] 为 [1, 2, 3, 4, 5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

示例 1：

输入：numbers = [3, 4, 5, 1, 2]
输出：1

示例 2：

输入：numbers = [2, 2, 2, 0, 1]
输出：0

提示：

• n == numbers.length
• 1 <= n <= 5000
• -5000 <= numbers[i] <= 5000
• numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

Solution

暴力遍历

遍历数组，直到找到一个index，其元素值小于前面的一个元素值，如果没有则返回第一个元素值。

二分查找

看代码

Code

暴力法

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    const len = numbers.length;
    if (len === 1) return numbers[0];

    for (let i = 0; i < len; i++) {
        if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
    }
    return numbers[0];
};

二分查找

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    const len = numbers.length;

    if (len === 1) return numbers[0];

    let left = 0,
        right = len - 1;
    while (left < right) {
        let mid = left + Number.parseInt((right - left) / 2);

        if (numbers[mid] > numbers[right]) {
            left = mid + 1;
        } else if (numbers[mid] < numbers[right]) {
            right = mid;
        } else {
            right--;
        }

    }
    return numbers[left];
};

Trap

注意：被旋转的数组后半部分最后一个值小于等于前半部分第一个值。