题目描述
思路解析
一句话答案：LeetCode 33 搜索旋转排序数组的解法是改良二分查找：mid 把区间切成两半后必有一半是完整有序的（nums[l] <= nums[mid] 则左半有序，否则右半有序），再看 target 是否落在有序半的值域内——在就收缩到有序半，不在就去另一半。每步稳定砍掉一半区间，时间 O(log n)、空间 O(1)。
搜索旋转排序数组在问什么
一个原本升序、无重复元素的数组，在某个位置被整体旋转过（比如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]），给定 target，要求返回它的下标，不存在返回 -1，并且明确要求 O(log n)。这个复杂度要求本身就是提示：线性扫描被排除了，题目在逼你把二分查找改造到「不完全有序」的数组上。
普通二分为什么在旋转数组上失效
二分查找的根基是单调性：数组有序时，拿 nums[mid] 和 target 比一下大小，就知道目标只可能在左半或右半，方向唯一。旋转之后数组整体不再单调，中间藏着一个从最大值跌到最小值的断点，nums[mid] 比 target 大还是小不再指示方向——目标可能在任意一侧。直接套普通二分，会在错误的一半里越找越偏。
关键观察：mid 切两半，必有一半有序
救回二分的观察是：旋转数组只有一个断点，而 mid 把区间切成两半，断点只能落进其中一半——另一半必然是完整有序的。而且哪半有序当场可判：nums[l] <= nums[mid] 说明从 l 到 mid 一路没有跨过断点，左半 [l..mid] 有序；反之断点在左半，右半 [mid..r] 有序。
拿示例 [4,5,6,7,0,1,2] 找 target = 0 验证：首轮 mid 落在 7，nums[0] = 4 <= 7，左半 [4,5,6,7] 有序，0 不在 4 到 7 之间，于是放心奔右半——一步就丢掉了一半。
为什么查有序半的值域就能安全决策
有序半的价值在于它的值域是明确的闭合范围：左半有序时值域是 nums[l] 到 nums[mid]，右半有序时是 nums[mid] 到 nums[r]。于是判断变成一道二选一：target 落在这个范围里，它若存在就只能在有序半，收缩过去；不在范围里，则只可能藏在另一半（那半虽然乱，但排除法保证方向正确）。
每一轮无论走哪个分支，区间都严格减半，这就是 O(log n) 的来源。二分不怕那一半内部乱，怕的是不知道往哪走——有序半的值域恰好提供了永远可靠的路标。
复杂度与边界符号怎么写才不错
时间 O(log n)，最多 log₂n 轮；空间 O(1)，只用 l、mid、r 三个下标。边界符号是这题的雷区：判左半有序要用 nums[l] <= nums[mid]（含等号，兼容区间只剩一个元素的情形）；判值域时左半用 nums[l] <= target < nums[mid]、右半用 nums[mid] < target <= nums[r]——mid 本身已经在循环开头和 target 比过、确认不相等，所以范围要把 mid 排除、把端点含进来。循环条件必须是 l <= r，写成 l < r 会在区间只剩一个元素时漏查、误报 -1。另外，若数组允许重复元素（LeetCode 81），nums[l] 等于 nums[mid] 时判不出哪半有序，只能逐格收缩，最坏退化到 O(n)——本题保证无重复，才有稳定的对数复杂度。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心口诀：mid 切两半 → 必有一半有序 → 看 target 在不在有序半范围 → 在就去有序半、不在去另一半。下面每帧都在套它。
mid=5（值 0）。因为 nums[l]=14 > nums[mid]=0，左半被旋转断了，反而是右半 [5..11] 有序（0…11）。target 11 正好落在这个有序半的范围里，所以缩到右半。
把左指针挪到 mid+1=6，灰掉 mid 及其左边整片，搜索区间收缩到 [6, 11]。
mid=8（值 4）。因为 nums[l]=1 ≤ nums[mid]=4，左半 [6..8] 是有序的（1…4）。target 11 不在这个有序半的范围里，所以去另一半（右半）。
把左指针挪到 mid+1=9，灰掉 mid 及其左边整片，搜索区间收缩到 [9, 11]。
mid=10（值 9）。因为 nums[l]=6 ≤ nums[mid]=9，左半 [9..10] 是有序的（6…9）。target 11 不在这个有序半的范围里，所以去另一半（右半）。
把左指针挪到 mid+1=11，灰掉 mid 及其左边整片，搜索区间收缩到 [11, 11]。
mid=11，nums[11]=11 正好等于 target 11，命中！返回下标 11。
命中的格子绿色高亮。每一步都把区间砍一半，4 步就锁定了答案下标 11，这就是 O(log n)。
mid=5（值 0）。因为 nums[l]=14 > nums[mid]=0，左半被旋转断了，反而是右半 [5..11] 有序（0…11）。target 2 正好落在这个有序半的范围里，所以缩到右半。
把左指针挪到 mid+1=6，灰掉 mid 及其左边整片，搜索区间收缩到 [6, 11]。
mid=8（值 4）。因为 nums[l]=1 ≤ nums[mid]=4，左半 [6..8] 是有序的（1…4）。target 2 正好落在这个有序半的范围里，所以缩到左半。
把右指针挪到 mid-1=7，灰掉 mid 及其右边整片，搜索区间收缩到 [6, 7]。
mid=6（值 1）。因为 nums[l]=1 ≤ nums[mid]=1，左半 [6..6] 是有序的（1…1）。target 2 不在这个有序半的范围里，所以去另一半（右半）。
把左指针挪到 mid+1=7，灰掉 mid 及其左边整片，搜索区间收缩到 [7, 7]。
mid=7，nums[7]=2 正好等于 target 2，命中！返回下标 7。
命中的格子绿色高亮。每一步都把区间砍一半，4 步就锁定了答案下标 7，这就是 O(log n)。
mid=5（值 0）。nums[l]=14 > nums[mid]=0，右半 [5..11] 有序。target 5 落在有序半范围内，缩到右半。
左指针挪到 6，区间收缩到 [6, 11]。
mid=8（值 4）。nums[l]=1 ≤ nums[mid]=4，左半 [6..8] 有序。target 5 不在有序半范围内，去另一半（右半）。
左指针挪到 9，区间收缩到 [9, 11]。
mid=10（值 9）。nums[l]=6 ≤ nums[mid]=9，左半 [9..10] 有序。target 5 不在有序半范围内，去另一半（右半）。
左指针挪到 11，区间收缩到 [11, 11]。
mid=11（值 11）。nums[l]=11 ≤ nums[mid]=11，左半 [11..11] 有序。target 5 不在有序半范围内，去另一半（右半）。
左指针挪到 12，区间收缩到 [12, 11]。
当左指针越过了右指针、区间变空，说明 target 5 确实不在数组里，返回 -1。二分天然不会漏判也不会误报。
边界先想清：单元素、找不到都要能干净返回，不能因为旋转而误判。
两个高频追问：有重复怎么办、能否先定位旋转点。
参考代码
def search(nums, target): l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] == target: return mid if nums[l] <= nums[mid]: # 左半有序 if nums[l] <= target < nums[mid]: r = mid - 1 # target 在有序左半 else: l = mid + 1 else: # 右半有序 if nums[mid] < target <= nums[r]: l = mid + 1 # target 在有序右半 else: r = mid - 1 return -1复杂度
- 时间：O(log n)，每步砍掉一半区间，最多 log₂n 步
- 空间：O(1)，只用 l、mid、r 三个下标，不开额外数组
易错点
面试追问把动画讲成自己的话
追问如果数组里有重复元素（LC81）会怎样？
追问能不能先找到旋转点再二分？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
基于时间的键值存储
LeetCode 981 · 中等 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题