旋转数组搜索
查找 · 断崖上的二分 · 至少一半有序
被旋转的有序数组
[1..17] 从中间某处「旋转」一下变成 [13, 15, 17, 1, 3, 5, 7, 9, 11]——柱形图里那道断崖一眼可见。整体没序了， 基础二分的「和中点比大小」直接失灵：中点比目标大，目标却可能在右边。
关键引理：mid 切开的两半，至少一半完好有序
断崖只有一道，mid 落在它的某一侧——于是另一侧必然完好有序。判断很便宜：a[lo] ≤ a[mid] 就是左半有序，否则右半有序。有序半的范围是明明白白的（首尾即最小最大），看目标在不在里面：在，就进有序半；不在，目标必在另一半。每步照样扔掉一半。下面两次查找：target = 5（先进右半再进左半）、target = 15（有序半不含目标、整半排除）。右侧代码随每一步同步高亮。
有序数组被旋转过：[1..17] 断成 [13,15,17 | 1,3,5,7,9,11]，柱形里那道「断崖」清晰可见。找 target = 5：关键引理——mid 切开的两半，至少一半完好有序
1function searchRotated(a: number[], t: number): number {
2 let lo = 0, hi = a.length - 1;
3 while (lo <= hi) {
4 const mid = (lo + hi) >> 1;
5 if (a[mid] === t) return mid; // 命中
6 if (a[lo] <= a[mid]) { // 左半有序
7 if (a[lo] <= t && t < a[mid]) hi = mid - 1; // 在有序左半
8 else lo = mid + 1; // 否则去右半
9 } else { // 右半有序
10 if (a[mid] < t && t <= a[hi]) lo = mid + 1; // 在有序右半
11 else hi = mid - 1; // 否则去左半
12 }
13 }
14 return -1;
15}
断崖17 ↘ 1（idx 2/3 之间）
target5
[lo, hi][0, 8]
mid—
判半—
1 / 8
细节与边界
判半：a[lo] ≤ a[mid] ⟹ 左半 [lo, mid] 有序；否则右半 [mid, hi] 有序。
范围判断：左半有序时看 a[lo] ≤ t < a[mid]；右半有序时看 a[mid] < t ≤ a[hi]。
复杂度：每步一次判半 + 一次范围判断，仍是 O(log n)。
坑：含重复元素时 a[lo] == a[mid] 无法判半（只能 lo++），最坏退化 O(n)。
范围判断：左半有序时看 a[lo] ≤ t < a[mid]；右半有序时看 a[mid] < t ≤ a[hi]。
复杂度：每步一次判半 + 一次范围判断，仍是 O(log n)。
坑：含重复元素时 a[lo] == a[mid] 无法判半（只能 lo++），最坏退化 O(n)。
同样的「断崖」思路还能找旋转点（最小值位置：与 a[hi] 比较的二分）。至此二分已经在三种地形上跑过：全有序、带重复、被旋转——下一站彻底跳出数组，在答案空间上二分（二分答案），那是查找大类的收官技。