京公网安备11010502063487号一个升序、元素互不相同的数组，在某个位置被旋转了一下（例如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]）。给定一个目标值，在 O(log n) 时间内找到它的下标，找不到返回 -1。关键观察：把旋转数组从中间劈开，左右两半里至少有一半是有序的。每次二分先判断哪一半有序，再看目标落不落在有序的那一半里，据此丢掉一半。本文用真实数据展示"忽略旋转、当普通二分"会错多少，实测二分和线性扫描的耗时，给出五种语言的实现，并把每一步二分做成分步演示。
完整题目见官方页面（链接在文末）。基准解是线性查找（list.index），与二分完全不同。一共 14 组用例，覆盖：官方示例、目标不存在、单个元素、两个元素、未旋转的数组、旋转点在头或尾：
输入 [[4,5,6,7,0,1,2],0] 输出 4 输入 [[4,5,6,7,0,1,2],3] 输出 -1 输入 [[1],0] 输出 -1 输入 [[1],1] 输出 0 输入 [[1,3],3] 输出 1 输入 [[3,1],1] 输出 1
普通二分假设整个数组升序，看 nums[mid] 与 target 的大小就能决定往哪边找。旋转数组不满足这个假设：nums[mid] < target 时目标可能在左边，也可能在右边。我把所有可能的情形都枚举了一遍：长度为 n 的数组共有 n 种旋转，每种旋转下取数组里的每个值作为目标，共 n × n 种，逐一对比普通二分和线性查找的答案：
# 忽略旋转、当普通有序数组二分的写法 长度 4：所有 4 种旋转 × 4 个目标共 16 种，普通二分答错 4 种（25.0%），旋转二分答错 0 种 长度 6：所有 6 种旋转 × 6 个目标共 36 种，普通二分答错 11 种（30.6%），旋转二分答错 0 种 长度 8：所有 8 种旋转 × 8 个目标共 64 种，普通二分答错 18 种（28.1%），旋转二分答错 0 种 长度 10：所有 10 种旋转 × 10 个目标共 100 种，普通二分答错 31 种（31.0%），旋转二分答错 0 种 例：[4, 5, 6, 7, 0, 1, 2] 找 0：普通二分 -> -1，solve -> 4
对长度 4 到 10 的所有情形，普通二分都有 25% 到 31% 的情形答错，而本文的旋转二分一个都没错。例如 [4, 5, 6, 7, 0, 1, 2] 找 0：普通二分返回 -1，正确答案是 4。这个枚举只针对元素互不相同、长度 4 到 10 的数组，覆盖了这个长度上的全部旋转和全部存在的目标，不含目标不存在的情形。
每次取中点 mid。如果 nums[lo] <= nums[mid]，说明左半 [lo, mid] 有序（旋转点不在里面）：若 target 落在 [nums[lo], nums[mid]) 内，就在左半找，否则去右半；反过来右半 [mid, hi] 有序：若 target 落在 (nums[mid], nums[hi]] 内就在右半找，否则去左半。Java、Go、C++ 里中点写成 lo + (hi - lo) / 2，避免 lo + hi 溢出（下一题会用真实运行展示这个溢出）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # 左半 [lo, mid] 是有序的 if nums[lo] <= target < nums[mid]: # target 落在有序的左半里 hi = mid - 1 else: lo = mid + 1 else: # 否则右半 [mid, hi] 是有序的 if nums[mid] < target <= nums[hi]: # target 落在有序的右半里 lo = mid + 1 else: hi = mid - 1 return -1
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[4,5,6,7,0,1,2],0] → 4 [[4,5,6,7,0,1,2],3] → -1 [[1],0] → -1 [[1],1] → 0 [[1,3],3] → 1 [[3,1],1] → 1
Java · 解法代码class Solution { public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if (nums[mid] == target) return mid; if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 是有序的 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 否则右半 [mid, hi] 是有序的 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[4,5,6,7,0,1,2],0] → 4 [[4,5,6,7,0,1,2],3] → -1 [[1],0] → -1 [[1],1] → 0 [[1,3],3] → 1 [[3,1],1] → 1
Go · 解法代码func search(nums []int, target int) int { lo, hi := 0, len(nums)-1 for lo <= hi { mid := lo + (hi-lo)/2 if nums[mid] == target { return mid } if nums[lo] <= nums[mid] { // 左半 [lo, mid] 是有序的 if nums[lo] <= target && target < nums[mid] { hi = mid - 1 } else { lo = mid + 1 } } else { // 否则右半 [mid, hi] 是有序的 if nums[mid] < target && target <= nums[hi] { lo = mid + 1 } else { hi = mid - 1 } } } return -1 }
$ go build -o bin . && ./bin < cases.jsonl [[4,5,6,7,0,1,2],0] → 4 [[4,5,6,7,0,1,2],3] → -1 [[1],0] → -1 [[1],1] → 0 [[1,3],3] → 1 [[3,1],1] → 1
JavaScript · 解法代码function search(nums, target) { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 是有序的 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 否则右半 [mid, hi] 是有序的 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; }
$ node run.js < cases.jsonl [[4,5,6,7,0,1,2],0] → 4 [[4,5,6,7,0,1,2],3] → -1 [[1],0] → -1 [[1],1] → 0 [[1,3],3] → 1 [[3,1],1] → 1
C++ · 解法代码#include <vector> using namespace std; class Solution { public: int search(vector<int>& nums, int target) { int lo = 0, hi = (int)nums.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if (nums[mid] == target) return mid; if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 是有序的 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 否则右半 [mid, hi] 是有序的 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[4,5,6,7,0,1,2],0] → 4 [[4,5,6,7,0,1,2],3] → -1 [[1],0] → -1 [[1],1] → 0 [[1,3],3] → 1 [[3,1],1] → 1
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
数组长度分别为 1 万、10 万、100 万、300 万，旋转点取在三分之一处，每次查找的目标是数组的最后一个元素（线性扫描要走完整个数组），每个规模取三次中最快的一次：
数组长度 n（找最后一个元素） | 暴力解 | 本文解法
10000 | 0.160 ms | 0.002 ms
100000 | 1.573 ms | 0.003 ms
1000000 | 15.992 ms | 0.014 ms
3000000 | 47.504 ms | 0.017 ms线性查找（这里是 C 实现的 list.index）随长度线性增长，300 万时约 47.5ms；二分只需要约 log₂(300万) ≈ 22 次比较，耗时在微秒量级，300 万时约 0.017ms，约 2800 倍。二分的耗时在这个范围内几乎不变，小规模上的读数受计时精度影响，没有细究。
Python 版本另外和线性查找做了随机对拍，数组是随机的互不相同的升序数组经随机旋转得到，目标 60% 取自数组内、40% 随机取（可能不存在）：
随机对拍 20000 组（长度 1 到 12、互不相同的升序数组，随机旋转，target 60% 取自数组内、40% 随机取（可能不存在）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [4, 5, 6, 7, 0, 1, 2] 找 0。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。第一次 mid = 3：左半 [4, 5, 6, 7] 有序，0 不在里面，去右半；第二次 mid = 5，左半 [0, 1] 有序，0 在里面，去左半，下一次直接命中。