题目

思路

一句话：每轮先判断哪半段是完整的升序区间，再只用这段的两个端点判断 target 是否落在其中；在则留这半段，不在则去另一半。

最直白的做法是线性扫描：从左到右逐个找 target，一定能得到正确答案，但时间是 O(n)，不满足题目硬性要求的 O(log n)。

那能不能直接套普通二分？不行。普通二分的依据是“整个区间有序”，因此拿 nums[mid] 与 target 比就能决定向左还是向右；旋转后全局有序被打破。例如 [4,5,6,7,0,1,2] 中 nums[mid]=7、target=0，虽然 target < 7，但它却在 mid 的右侧，普通二分会走错方向。

关键观察：把当前区间 [left, right] 从中点切开后，左右两半里至少有一半是完全升序的。因为旋转只切一次，断崖最多会落在其中一半里，另一半必然没被切断。判断方法很便宜：

• 若 nums[left] ≤ nums[mid]，说明 [left, mid] 没有跨越断崖，左半段有序。
• 否则断崖在左半段，右半段 [mid, right] 一定有序。

有序的那半段像一个“可靠的指南针”：它的两个端点能明确圈出值域。若 target 在这个值域内，就去这半段继续找；否则 target 只可能在另一半。每轮据此安全丢掉一半，最终 O(log n)。元素互不相同保证了 ≤ 判断无歧义。

解法

维护一个始终“可能包含 target”的区间 [left, right]：

1. 令 mid = left + (right - left) / 2。
2. 若 nums[mid] == target，直接返回 mid。
3. 若 nums[left] ≤ nums[mid]（左半有序）：当 nums[left] ≤ target < nums[mid
   🔒

   本篇为付费内容

   您已阅读试读部分，购买后即可解锁全文。

   ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。