C++实现旋转数组的二分查找

前言

「旋转数组」指的是把一个升序数组在某个位置切开、把后段接到前面，例如[0,1,2,4,5,6,7]在索引 3 处旋转得到[4,5,6,7,0,1,2]。整体不再有序，但局部仍然有序，这个「两段各自有序」的结构正是二分查找还能工作的原因。

典型误解是认为「数组无序就不能二分」。实际上二分的本质不是「数组有序」，而是「能根据中点信息排除一半候选」。旋转数组里，中点把区间分成两半，其中至少有一半是严格升序的；判断目标值是否落在这段有序区间内，就能决定舍弃哪一半。

另一个高频错误是边界条件写错：lo <= hi还是lo < hi、hi = mid还是hi = mid - 1、比较时用<还是<=。这些不是风格问题，写错就会漏掉元素或死循环。本文会给出一个经过逐分支推演的版本，并单独讨论含重复元素时为什么会退化到 O(n)。

一、核心观察：至少一半有序

设当前区间为[lo, hi]，中点mid = lo + (hi - lo) / 2。由于数组是由一个升序数组旋转而来，a[lo..mid]与a[mid..hi]中至少有一段是升序的：

• 
  
• 若a[lo] <= a[mid]，则左半段[lo, mid]升序；
• 
  
• 否则a[lo] > a[mid]，说明旋转点落在左半段，右半段[mid, hi]升序。
• 
  

注意这里用的是<=而不是<。当a[lo] == a[mid]时（长度为 1 或元素重复），把它归入「左半段有序」不会造成错误，因为此时左半段只有一个元素或全部相等，仍然满足升序。

确定有序的一半后，判断目标是否落在该半段的值域内。若在，就去那一半继续找；若不在，目标只可能在另一半。这一步把问题规模减半，因此复杂度是 O(log n)。

二、完整实现

// 适用于 C++17
#include <iostream>
#include <vector>

// 返回目标值的下标，找不到返回 -1；假设数组元素互不相同
int searchRotated(const std::vector<int>& a, int target) {
int lo = 0;
int hi = static_cast<int>(a.size()) - 1;

while (lo <= hi) {
const int mid = lo + (hi - lo) / 2; // 防止 lo + hi 溢出

if (a[mid] == target) {
return mid;
}

if (a[lo] <= a[mid]) {
// 左半段 [lo, mid] 升序
if (a[lo] <= target && target < a[mid]) {
hi = mid - 1; // 目标在左半段内部
} else {
lo = mid + 1; // 否则去右半段
}
} else {
// 右半段 [mid, hi] 升序
if (a[mid] < target && target <= a[hi]) {
lo = mid + 1; // 目标在右半段内部
} else {
hi = mid - 1;
}
}
}
return -1;
}

int main() {
std::vector<int> a{4, 5, 6, 7, 0, 1, 2};
std::cout << searchRotated(a, 0) << "\n"; // 期望 4
std::cout << searchRotated(a, 3) << "\n"; // 期望 -1
return 0;
}

逐个分支核对。a[lo] <= a[mid]为真时，左半段升序，值域是[a[lo], a[mid]]。因为a[mid] != target已经在前面的判断里排除，所以目标落在左半段的条件是a[lo] <= target < a[mid]，两个边界都取得到。若满足，hi = mid - 1；否则目标要么大于a[mid]，要么小于a[lo]，两种情况下都只能去右半段，lo = mid + 1。

右半段对称：值域是[a[mid], a[hi]]，排除a[mid]后条件是a[mid] < target <= a[hi]。满足则lo = mid + 1，否则hi = mid - 1。

mid用lo + (hi - lo) / 2而不是(lo + hi) / 2，是为了避免两个大下标相加溢出。对int来说，数组长度超过十亿时才可能出问题，但这是个无需成本的好习惯。

循环条件是lo <= hi，因为区间是闭区间，lo == hi时还有一个元素需要检查。若写成lo < hi，最后一个元素会被漏掉。相应地，收缩时用mid ± 1而不是mid，否则区间不缩小，会死循环。

三、手工推演

以a = [4,5,6,7,0,1,2]、target = 0为例。初始lo = 0、hi = 6。

第一轮mid = 3，a[3] = 7，不等于 0。a[lo] = 4 <= 7，左半段有序。判断4 <= 0为假，lo = 4。

第二轮lo = 4、hi = 6，mid = 5，a[5] = 1，不等于 0。a[4] = 0 <= 1，左半段[4,5]有序。判断0 <= 0 && 0 < 1为真，hi = 4。

第三轮lo = 4、hi = 4，mid = 4，a[4] = 0，命中，返回 4。正确。

再以target = 3为例。第一轮同上，lo = 4。第二轮mid = 5，a[5] = 1，a[4] = 0 <= 1，判断0 <= 3 && 3 < 1为假，lo = 6。第三轮lo = 6、hi = 6，mid = 6，a[6] = 2，不等于 3。a[6] = 2 <= 2，左半段有序，判断2 <= 3 && 3 < 2为假，lo = 7。循环结束，返回 −1。正确。

这两个例子覆盖了「命中」与「未命中」两条路径，也覆盖了「去左半段」与「去右半段」两个分支。自己实现时，建议至少再补一个「旋转点为 0」（数组完全有序）和「旋转点为 n−1」（只旋转一位）的用例。

四、含重复元素的情况

当数组允许重复元素时，a[lo] <= a[mid]这个判断可能失效。例如[1,1,1,1,1,1]中，a[lo] == a[mid] == a[hi]，无论目标是什么，都无法判断哪一半有序，也无法排除任何一半。

此时只能「收缩边界」：既然a[lo] == a[mid] == a[hi]，且a[mid] != target，那么a[lo]与a[hi]都不可能是目标，直接++lo; --hi;跳过这两个元素。最坏情况下（大量重复），每次只缩小两个元素，复杂度退化为 O(n)。

// 适用于 C++17，允许重复元素
int searchRotatedWithDups(const std::vector<int>& a, int target) {
int lo = 0;
int hi = static_cast<int>(a.size()) - 1;

while (lo <= hi) {
const int mid = lo + (hi - lo) / 2;
if (a[mid] == target) {
return mid;
}
if (a[lo] == a[mid] && a[mid] == a[hi]) {
++lo;
--hi;
} else if (a[lo] <= a[mid]) {
if (a[lo] <= target && target < a[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (a[mid] < target && target <= a[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}

++lo; --hi;之后不能直接continue到下一轮而不做别的，因为循环条件会重新判断，这是正确的。但要注意，当lo与hi相邻时，++lo与--hi可能让lo > hi，循环自然结束，不会越界。

这段代码在a[lo] == a[mid] == a[hi]时，只排除了两个端点，中间的元素并未检查。这不会漏解，因为如果目标在中间，后续的二分仍会在缩小后的区间里找到它——除非中间全是相同值且目标不在其中，那时区间会逐步缩小直到为空，返回 −1。

五、相关变体

同一套「找有序半边」的思路可以解决几个相关问题：

查找最小值的写法更简单，不需要判断目标：

// 适用于 C++17，元素互不相同
int findMin(const std::vector<int>& a) {
int lo = 0;
int hi = static_cast<int>(a.size()) - 1;
while (lo < hi) {
const int mid = lo + (hi - lo) / 2;
if (a[mid] > a[hi]) {
lo = mid + 1; // 最小值在右半段
} else {
hi = mid; // 最小值在左半段（含 mid）
}
}
return a[lo];
}

这里循环条件是lo < hi，收缩时hi = mid而不是mid - 1，因为mid本身可能就是最小值。调用前必须保证数组非空，否则a[lo]越界。

常见坑点

坑点一：以为旋转数组完全无序，放弃二分。

// ❌ 错误：线性扫描，浪费了「两段有序」的结构
for (int i = 0; i < n; ++i) if (a[i] == target) return i;

// ✅ 正确：利用有序半边做二分
if (a[lo] <= a[mid]) { /* 左半有序 */ } else { /* 右半有序 */ }

坑点二：判断有序半边时用<而不是<=。

// ❌ 错误：a[lo] == a[mid] 时进入 else 分支，错误地认为右半有序
if (a[lo] < a[mid]) { /* ... */ }

// ✅ 正确：相等时归入左半有序
if (a[lo] <= a[mid]) { /* ... */ }

坑点三：目标值范围的边界写成开区间。

// ❌ 错误：漏掉 target == a[lo] 的情况
if (a[lo] < target && target < a[mid]) { /* ... */ }

// ✅ 正确：左边界包含，右边界排除（a[mid] 已判过）
if (a[lo] <= target && target < a[mid]) { /* ... */ }

坑点四：循环条件与收缩方式不匹配。

// ❌ 错误：lo < hi 配 hi = mid - 1，可能漏掉最后一个元素
while (lo < hi) { /* ... */ hi = mid - 1; }

// ✅ 正确：闭区间配 lo <= hi 与 mid ± 1
while (lo <= hi) { /* ... */ hi = mid - 1; }

坑点五：mid用(lo + hi) / 2计算。

// ❌ 错误：大下标相加可能溢出，溢出是 UB
int mid = (lo + hi) / 2;

// ✅ 正确：用差值计算
int mid = lo + (hi - lo) / 2;

坑点六：含重复元素时仍声称 O(log n)。

// ❌ 错误：全相同数组下每次只缩小两个元素，实际是 O(n)
// 在文档里写「时间复杂度 O(log n)」

// ✅ 正确：注明互不相同为 O(log n)，允许重复时最坏 O(n)

坑点七：对空数组直接取a.size() - 1。

// ❌ 错误：size 为 0 时无符号减法回绕，hi 变成极大值
int hi = a.size() - 1;

// ✅ 正确：先判空，或转成有符号再减
if (a.empty()) return -1;
int hi = static_cast<int>(a.size()) - 1;

总结

旋转数组的二分查找并不需要新算法，只是把「数组有序」换成了「局部有序」。写的时候把「哪半有序、目标在不在其中」这两问按顺序回答清楚，再把区间开闭与收缩方式对齐，代码自然就对了。