题目

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

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

给你一个可能存在 重复 元素值的数组 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]] 。

示例：

输入：numbers = [3,4,5,1,2]
输出：1
复制代码

分析

做这道题还是花了有点多时间的，踩坑无数，现在来一起复盘一下

首先这是一个半有序数组，可以优先考虑使用二分查找

之前有个误区，认为二分查找必须是有序数组才能使用，实际上只要满足一定的条件，就可以使用二分查找

二分查找本质是将查找区间由中间分为两份，只要能总结出，目标值在其中哪一部分，就可以使用二分查找

回到这道题中

需要我们分析出目标值在我们分割的区间中有什么特点

旋转点右侧元素大于旋转点左侧元素

如果使用二分法将数组切分，以 mid 为中点，把数组切成两部分

即 3 个端点：left = 0; right = numbers.length - 1; mid = (left + right) >> 1

[leff, mid)

[mid, right]

那么根据中间点 mid 的大小，会有三种情况

• nums[mid] < nums[right]

最小值就在 [left, mid] 之间

• nums[mid] > nums[right]

最小值就在 [mid, right]之间

• 两者相等？

这个地方就有坑了，由于可能存在多个相同的值，无法直接确定就是最小值

这里就需要逐步逼近了，让右端点减1再继续迭代，这样最后的右端点就是我们所求的最小值

实现

function minArray(numbers: number[]): number {
    let l_idx: number = 0
    let r_idx: number = numbers.length - 1
    while(l_idx < r_idx) {
        const mid: number = (l_idx + r_idx) >> 1
        if (numbers[mid] < numbers[r_idx]) {
            // 【l_ridx - mid】
            r_idx = mid
        } 
        else if (numbers[mid] > numbers[r_idx]) {
            // 【mid - r_idx】
            l_idx = mid + 1
        }
        else {
            r_idx --
        }
    }
    return numbers[r_idx]
};