96.寻找旋转排序数组中的最小值

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转后，得到输入数组。

例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

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

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

• 输入：nums = [3,4,5,1,2]
• 输出：1
• 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

• 输入：nums = [4,5,6,7,0,1,2]
• 输出：0
• 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

• 输入：nums = [11,13,15,17]
• 输出：11
• 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

思路

旋转后的数组有一个特点：它由两段递增的子数组组成。

比如 [4,5,6,7,1,2,3]：

• 前半段：[4,5,6,7]→ 递增

• 后半段：[1,2,3]→ 递增

• 最小值就是两段的分界点（也就是后半段的开头）

怎么用二分找这个分界点？

我们比较中间元素和最右边的元素：

1. 如果 nums[mid] > nums[right]​

   → 说明最小值在右半段（因为左半段的值都比右半段大）

   → 往右边找：left = mid + 1

2. 如果 nums[mid] < nums[right]​

   → 说明最小值在左半段（包括mid本身也可能是最小值）

   → 往左边找：right = mid

3. 不断缩小范围，直到 left == right，那个位置就是最小值

fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1

    while (left < right) {  // 注意这里是 < 不是 <=
        val mid = left + (right - left) / 2

        // 比较中间值和最右边的值
        if (nums[mid] > nums[right]) {
            // 最小值在右半段
            left = mid + 1
        } else {
            // 最小值在左半段（包含mid）
            right = mid
        }
    }

    // 此时 left == right，就是最小值的位置
    return nums[left]
}

总结一句话：旋转数组找最小值，就是比较中间和最右，谁小往谁那边靠，直到左右指针相遇。

复杂度

• 时间复杂度: O(log n) — 标准的二分查找
• 空间复杂度: O(1) — 只用了几个变量

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!