描述

有一个长度为 n 的非降序数组，比如[1, 2, 3, 4, 5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3, 4, 5, 1, 2]，或者[4, 5, 1, 2, 3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1) ，时间复杂度：O(logn)

链接

Nowcoder BM21 旋转数组的最小数字

示例

[3,4,5,1,2] => 1
[2,2,2,0,1] => 0
[1,3,3] => 1
[3,100,200,3] => 3

题解

暴力解法

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
function minNumberInRotateArray(nums) {

    // write code here
    let min = nums[0];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;

}
module.exports = {

    minNumberInRotateArray: minNumberInRotateArray,

};

二分法

// 方法：二分法（推荐使用）
// 知识点：分治

// 分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。
// 具体做法：

// step 1：双指针指向旋转后数组的首尾，作为区间端点。
// step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。
// step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。
// step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。
// step 5：通过调整区间最后即可锁定最小值所在。
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
function minNumberInRotateArray(nums) {
    // write code here
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        // 非降序数组进行了旋转
        if (nums[mid] === nums[right]) {
            if (mid === right) return nums[mid];
            right = right - 1;
        }
        // 中间值大于右边 那最小值应该是在右边
        // 如果按照升序看，可以left直接向右多移动一位
        else if (nums[mid] > nums[right]) {
            left = mid + 1;
        }
        // 中间值小右边 那最小值应该是在左边
        // 因为数组是非降序，右侧向左移动的时候需要小心，避免直接跨过最小值
        else {
            right = mid;
        }
    }
}
module.exports = {
    minNumberInRotateArray: minNumberInRotateArray,
};