LeetCode 33 搜索旋转排序数组：每轮先认出哪一半有序，等号不能少

LeetCode 33：一个升序、元素互不相同的数组，在某个位置被「转」了一下，比如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。给一个 target，要求 O(log n) 找到它的下标，找不到返回 -1。

普通二分依赖整段有序，这里整段已经不有序了。这篇的重点是：为什么仍然能二分，以及判断「哪一半有序」时那个等号为什么不能省。二分本身的窗口写法（闭区间、mid 的算法、循环条件）在 二分查找的中点和窗口 里讲过，这里直接沿用，不再展开。

这题有两种常见写法：一种是先二分找到旋转点，再在有序的那一段里做普通二分；另一种是每一轮先判断 mid 两侧哪一半有序，再决定往哪边收缩。两种都是 O(log n)。本文先讲第二种，它只有一个循环，但判断「左半有序」的那一行少写一个等号就会出错，下文用随机对拍给出具体的出错数量。

旋转数组长什么样

把 [4,5,6,7,0,1,2] 的值按下标画出来：

值
7 |          ●
6 |       ●
5 |    ●
4 | ●
2 |                         ●
1 |                      ●
0 |                   ●
  +--+--+--+--+--+--+--+--
    0  1  2  3  4  5  6   下标
    └── 左段 ──┘ └ 右段 ┘

它是两段上升的折线，左段整体比右段高，中间有一处断崖。断崖在哪，事先不知道。

关键观察：随便在 [lo, hi] 里取一个 mid，把区间切成 [lo, mid] 和 [mid, hi] 两半，断崖最多只落在其中一半里。另一半一定是完整的上升段。对有序的那一半，判断 target 在不在里面，只需要比较两个端点；不在，就去另一半。每轮扔掉一半，所以还是 O(log n)。

怎么认出哪一半有序？看两端：a[lo] <= a[mid] 说明从 lo 到 mid 没跨过断崖，左半有序；否则断崖在左半里，右半 [mid, hi] 有序。

逐轮状态：找 0 和找 3

下面两张表是 Playground 程序的实际输出整理。数组都是 [4,5,6,7,0,1,2]。

找 target = 0：

找 target = 3（不存在）：

注意第 2 轮：lo = 4 以后，窗口 [4, 6] 是 [0,1,2]，已经完全没有断崖了。算法并不需要知道这件事，它每轮照样判断哪半有序，只是此后每次判断都会得到「左半有序」，退化成普通二分。

区间写成左闭右开 [a[lo], a[mid])，是因为 a[mid] == target 已经在前面单独判断过，这里排除掉 a[mid] 本身。右半同理，写成 (a[mid], a[hi]]。

那个等号

左半有序的判断是 a[lo] <= a[mid]。很多人第一反应写成 <，理由是「元素互不相同，不可能相等」。

元素互不相同，但 lo 和 mid 可以是同一个下标。窗口只剩两个元素时，mid = lo + (hi - lo) / 2 向下取整，mid 就等于 lo。这时候 a[lo] < a[mid] 是假，程序会以为「左半无序、右半有序」，而左半其实只有一个元素，当然是有序的。

最小的反例是 [5,4] 找 4：

• lo = 0, hi = 1, mid = 0, a[mid] = 5，不是 4。
• 写 <：5 < 5 为假，进入右半分支，检查 a[mid] < target && target <= a[hi]，即 5 < 4，假，于是 hi = mid - 1 = -1，循环结束，返回 -1。
• 写 <=：5 <= 5 为真，左半 [5] 有序，4 不在 [5, 5) 里，去右边，lo = 1，下一轮命中。

对拍程序：随机生成长度 1 到 12、互不相同的升序数组，随机旋转，再把 target 从「最小值减 3」到「最大值加 3」逐个试，和线性查找对答案。种子固定，g++ 14.2 和 clang++ 19.1 结果一致：

错误率不到 1%，样例数据很可能全部通过，提交以后才在某个两元素的窗口上暴露。对拍跑出来的最短反例正是 [5,4] 找 4。

用例里最多跑了 4 轮（n ≤ 12）。另外在 100 万个元素、旋转三分之一的数组上抽样查找了约 2000 个目标，最多 20 轮，和普通二分的 ⌈log₂(10⁶)⌉ = 20 一样。

在这里跑

程序读 n、n 个整数和 target，每轮打印窗口和走向。输入先过一道检查：必须是互不相同的升序数组旋转得到的，否则直接报错，不去搜索一个不满足前提的数组。

本机 g++ 14.2、clang++ 19.1 加 -O2 -Wall -Wextra 编译无警告，默认 stdin 下两者输出相同：

round 1: lo=0 mid=3 hi=6 a[mid]=7  left sorted, go right
round 2: lo=4 mid=5 hi=6 a[mid]=1  left sorted, go left
round 3: lo=4 mid=4 hi=4 a[mid]=0  hit
index=4

把最后一行的 0 改成 3，会看到四轮里的前三轮都往右走，最后 index=-1。把 stdin 换成 2、5 4、4，第一轮 mid 等于 lo，正好走到那个等号；把程序里的 <= 改成 < 再跑，输出会变成 index=-1。

main 里先把结果存进 idx 再打印，是有意的。如果写成一行 std::cout << "index=" << search(a, target)，index= 会出现在所有轮次之前：C++17 规定 << 链从左往右求值，"index=" 先写进 cout，然后才调用 search，而 search 自己也在往 cout 写。本机两种编译器都是这个顺序。函数有输出副作用时，不要把它嵌在另一条输出语句中间。

另一种思路：先找断崖

也可以分两步：第一次二分找最小值的下标 k（断崖右侧），判断条件是 a[mid] > a[hi] 时最小值在 mid 右边，否则在 mid 或左边；然后根据 target 和 a[n-1] 的大小，决定在 [0, k-1] 还是 [k, n-1] 上做一次普通二分。总共两次 O(log n)。

两种写法复杂度相同。一次二分的版本代码更短，但每轮的分支多，等号容易写错；两步的版本每一步都是熟悉的形状，出错时更容易定位。找最小值那一步本身就是 LeetCode 153。讲解或面试演示时，先写两步版再说明可以合成一步，通常更稳。

有重复元素时：LeetCode 81

如果数组允许重复，a[lo] == a[mid] 就不再能说明左半有序。[1,3,1,1,1] 里 lo = 0, mid = 2，两端都是 1，断崖其实在左半里。用上面同一份 search 去找 3，本机实测返回 -1，但 3 就在下标 1；换成 [1,1,1,3,1]，同样的代码却能找到下标 3。两端相等的时候，信息不够判断断崖在哪一边。

LeetCode 81 的通常做法是：遇到 a[lo] == a[mid]，就只把 lo 加一，缩掉一个元素再看。这让最坏情况退化到 O(n)，比如几乎全是同一个值、只藏了一个不同值的数组。这是题目本身的下界，不是写法问题。Playground 里的程序在发现重复时直接拒绝输入，就是为了不把 33 的写法用到 81 的数据上。

和其他二分的关系

这题的结构可以概括为：每轮用 O(1) 的比较，判断答案在哪一半。普通二分的判断是「a[mid] 和 target 谁大」，这里多了一步「先看哪一半有序」。二分查找图解 里可以单步看窗口怎么收缩，换成旋转数组，只是每一步多问一个问题。

二分答案 是另一种扩展：不在数组里找值，而是在答案的取值范围上二分，前提是可行性随答案单调。三者的共同要求是：每一轮都能确定地扔掉一半，并且窗口一定会变小。

同样的判断也适用于写满之后的循环缓冲区：写指针绕回数组开头以后，按写入时间排列的元素在底层数组里就是一段旋转过的有序序列。只要每条记录的时间戳严格递增，就可以用本文的写法在 O(log n) 内按时间戳定位，不需要先把数组拷贝成有序的再查。