旋转数组搜索

查找 · 断崖上的二分 · 至少一半有序

被旋转的有序数组

[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 切开的两半，至少一半完好有序

细节与边界

判半：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[hi] 比较的二分）。至此二分已经在三种地形上跑过：全有序、带重复、被旋转——下一站彻底跳出数组，在答案空间上二分（二分答案），那是查找大类的收官技。