寻找旋转排序数组中的最小值 · 比较 mid 与 hi

二分 · 断点

旋转数组由两段递增区间组成,最小值是断点。通过比较 nums[mid] 与 nums[hi] 判断最小值在哪侧, 不是在找 target。

当前输入

nums = [3, 4, 5, 1, 2]

经典旋转数组,断点在下标 3,最小值 1

最小值

下标 3 · nums[3]

时间 O(log n)

空间 O(1)

题目两段递增二分执行收敛总结

Step 1/10 · ① 题目

题目 · 找旋转数组的最小值

当前发生了什么

题目 · 找旋转数组的最小值

给定旋转排序数组 nums = [3, 4, 5, 1, 2]。数组无重复元素,要求 O(log n) 时间找到最小值。

为什么这一步是对的

这题没有 target,目标是最小值本身,而不是在某个有序半段里定位 target。

执行表

步	lo	hi	mid	比较	操作
1	0	4	2	5 > 2	lo = mid + 1 = 3
2	3	4	3	1 ≤ 2	hi = mid = 3

数组舞台

3idx 0

4idx 1

5idx 2

1idx 3

2idx 4

代码同步 · Go

① 题目

1func findMin(nums []int) int {
2    lo, hi := 0, len(nums)-1
3 
4    for lo < hi {
5        mid := lo + (hi-lo)/2
6 
7        if nums[mid] > nums[hi] {
8            lo = mid + 1
9        } else {
10            hi = mid
11        }
12    }
13 
14    return nums[lo]
15}

本步不变量

最小值始终位于闭区间 [lo, hi] 中。

剧本时间线 · 共 10 步

循环不变量

1.最小值始终位于闭区间 [lo, hi] 中。
2.每次二分不是在找 target,而是在排除不可能包含最小值的一半区间。

面试 · 一段话讲清楚

我维护一个闭区间 [lo, hi],保证最小值一定在里面。每次取 mid,比较 nums[mid] 和 nums[hi]。如果 nums[mid] > nums[hi],说明 mid 位于左侧高值段,最小值在右侧,所以 lo = mid + 1;否则最小值在左侧并且 mid 可能就是答案,所以 hi = mid。循环结束时 lo == hi,返回 nums[lo]。时间复杂度 O(log n),空间 O(1)。

常见错误

错误 1：把 hi = mid 写成 hi = mid - 1
当 nums[mid] <= nums[hi] 时,mid 可能就是最小值,不能丢掉。
错误 2：套 LC33 的 target 判断模板
LC153 没有 target,只需要比较 nums[mid] 和 nums[hi]。
错误 3：忘记 LC153 没有重复元素
有重复元素时是 LC154,判断逻辑会变复杂。