题目描述
一个升序数组在某个点旋转过（比如 [0,1,2,4,5,6,7] 转成 [4,5,6,7,0,1,2]），在里面找 target，找到返回下标，没有返回 -1。
思路解析
挨个找当然行，可那就白白浪费了「旋转前本来有序」这个条件。题目都把有序明牌摆你面前了，必须把二分用起来。
转折：旋转数组虽整体无序，但从 mid 切两半，总有一半是完整升序（端点一比就知道：nums[l] ≤ nums[mid] 则左半有序）。认出有序半后，只要看 target 在不在那半的范围里就能决定丢哪边——照样每步砍一半。
准备 · 闭区间 [0,6]：搜索范围是整个数组，l=0、r=6。要找的 target = 0。
第 1 轮 · 取 mid：中点 mid=3 处是 7，不等于目标 0。先判断哪半有序。
第 1 轮 · 判有序半：比端点：nums[l]=4 ≤ nums[mid]=7，说明左半 [4,5,6,7] 是有序的。那就拿 target 和这个有序半的范围比。
第 1 轮 · target 不在有序半 → 去右半：0 不落在有序左半 [4,7] 里，所以它必在另一半。整个左半丢掉（灰），l 跳到 4。
第 2 轮 · 取 mid：只看右段 [0,1,2]。新中点 mid=5 处是 1，仍不等于 0。
第 2 轮 · 判有序半：同样先比端点：nums[4]=0 ≤ nums[5]=1，左半 [0,1] 有序。拿 target 和它的范围比。
第 2 轮 · target 在有序半 → 收右：这次 0 正好落在有序左半 [0,1] 里，所以去这半找：丢掉 mid 右边，r 收到 4。
第 3 轮 · 命中！：区间只剩一个，mid=4 处正好是 0 = target。返回下标 4。每轮都砍掉一半，所以是 O(log n)。
旋转数组的二分，核心就这一句：哪半有序看得出来（端点比一下），target 在不在那半也看得出来（范围比一下）。剩下交给二分。
参考代码（Python）
1l, r = 0, len(nums) - 1 # 闭区间 [l, r]
2while l <= r:
3 mid = (l + r) // 2
4 if nums[mid] == target: return mid
5 if nums[l] <= nums[mid]: # 左半有序
6 if nums[l] <= target < nums[mid]: r = mid - 1
7 else: l = mid + 1
8 else: # 右半有序
9 if nums[mid] < target <= nums[r]: l = mid + 1
10 else: r = mid - 1
11return -1复杂度分析
- 时间复杂度：O(log n) —— 每轮砍一半
- 空间复杂度：O(1) —— 几个指针
套路模板
骨架记牢：先比 nums[l] 和 nums[mid] 定有序半，再用「闭区间范围」判 target 落哪半。LC81（含重复）、LC153（找最小）都是它的变体。
1while l <= r:
2 mid = (l + r) // 2
3 if nums[mid] == target: return mid
4 if nums[l] <= nums[mid]: # 左半有序
5 if nums[l] <= target < nums[mid]: r = mid-1
6 else: l = mid+1
7 else: # 右半有序
8 if nums[mid] < target <= nums[r]: l = mid+1
9 else: r = mid-1易错点
- 错误写法：nums[l] < nums[mid] 判有序 → 正确写法：nums[l] <= nums[mid]（mid 和 l 可能相邻甚至重合，必须带等号，否则漏判）
- 错误写法：target 范围判断用开区间 → 正确写法：落点比较要把端点算进去（闭区间）（端点本身可能就是答案，漏了就找不到）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。