二分查找变体
二分查找是面试中最容易出错的基础算法。关键不是背模板，而是理解为什么是 O(log n)、什么时候能用、以及边界条件怎么处理。
面试考察点
面试官通过这道题想考察：
1. 你是否理解二分查找的本质——为什么是 O(log n)
2. 你是否能正确处理边界条件——循环什么时候退出
3. 你是否能理解各种变体的区别——左边界、右边界
4. 你是否能应对变形题——旋转数组、峰值问题
一、二分查找的本质
1.1 什么是二分查找？（入门级解释）
面试官追问："为什么二分查找是 O(log n)？"
二分查找的思想：
假设一本字典有 1000 页，我要找 "Apple" 在哪一页。
方法 A - 逐页翻：
第 1 页...第 2 页...第 3 页...直到找到
最坏情况：翻 1000 次
方法 B - 二分翻：
1. 翻到中间（第 500 页），发现 A 在前面
2. 翻到 250 页，发现 A 在后面
3. 翻到 375 页，命中！
翻了 3 次就找到了！
为什么这么快？
因为每次都排除掉一半的可能！
1000 页 → 500 页 → 250 页 → 125 页 → ...
第 10 次时，只剩 1 页了！
数学：2^10 = 1024
所以 1000 个元素，只需要 log₂(1000) ≈ 10 次
1.2 二分查找的核心原理
二分查找的前提：
1. 有序数组（或者可以二分的有界空间）
2. 能随机访问（数组可以用下标访问）
核心思想：
1. 在有序空间中，找中间位置
2. 比较中间元素和目标
3. 根据比较结果，排除一半空间
4. 在剩下的空间继续二分
1.3 为什么是 O(log n)？（面试必问）
时间复杂度分析：
假设数组有 n 个元素：
第1次二分：搜索空间 = n/2
第2次二分：搜索空间 = n/4
第3次二分：搜索空间 = n/8
...
第 k 次二分：搜索空间 = n/2^k
什么时候停止？
n/2^k ≤ 1
即 2^k ≥ n
k ≥ log₂(n)
所以最多需要 log₂(n) 次！
每次操作是 O(1)，总复杂度是 O(log n)！
二、标准二分查找
2.1 模板（理解原理后很简单）
面试官追问："你能手写一个二分查找吗？边界条件怎么处理？"
标准二分查找：
目标：在有序数组 nums 中找 target
核心：
- left = 0, right = len(nums) - 1
- 循环条件：left <= right（注意是 <=）
- 中间位置：mid = left + (right - left) // 2
过程：
1. 计算 mid
2. 如果 nums[mid] == target，找到！
3. 如果 nums[mid] < target，目标在右半边，left = mid + 1
4. 如果 nums[mid] > target，目标在左半边，right = mid - 1
关键理解：
- left <= right：还有搜索空间
- left = mid + 1：mid 已经被排除
- right = mid - 1：mid 已经被排除
2.2 图解过程
nums = [1, 3, 5, 7, 9, 11, 13]，找 target = 9
初始：left=0, right=6
Step 1: mid=(0+6)//2=3
nums[3]=7 < 9，目标在右边
left=4
[1, 3, 5] [7, 9, 11, 13]
↑
left=4
Step 2: mid=(4+6)//2=5
nums[5]=11 > 9，目标在左边
right=4
[1, 3, 5, 7] [9, 11, 13]
↑
right=4
Step 3: mid=(4+4)//2=4
nums[4]=9 == 9，找到！
返回 4
三、二分查找的变体
3.1 查找左边界（第一个等于 target 的位置）
面试官追问："如果数组有重复元素，怎么找第一个等于 target 的位置？"
问题：nums = [1, 2, 2, 2, 2, 3]，找 target=2 的左边界
普通二分找到的是中间的一个 2，但可能不是第一个。
左边界二分的关键：
当 nums[mid] >= target 时，继续往左找
当 nums[mid] < target 时，往右找
这样能找到第一个等于 target 的位置！
过程：
nums = [1, 2, 2, 2, 2, 3]，找左边界
Step 1: left=0, right=5, mid=2
nums[2]=2 >= 2，往左找
right=1
Step 2: left=0, right=1, mid=0
nums[0]=1 < 2，往右找
left=1
Step 3: left=1, right=1, mid=1
nums[1]=2 >= 2，往左找
right=0（right < left，退出）
返回 left=1，这就是左边界！
验证：nums[1] = 2，第一个等于 2 的位置是 1 ✓
3.2 查找右边界（最后一个等于 target 的位置）
面试官追问："那怎么找最后一个等于 target 的位置？"
右边界二分的逻辑：
当 nums[mid] <= target 时，继续往右找
当 nums[mid] > target 时，往左找
这和左边界是"镜像"的关系！
四、常见变形题
4.1 搜索旋转排序数组（LeetCode 33）
考察点：二分查找的灵活应用
问题：数组原本有序，经过旋转后变成：
[4,5,6,7,0,1,2]，找 target=0
思路：
旋转后的数组可以分成两段有序数组：
- [4,5,6,7] 有序
- [0,1,2] 有序
关键洞察：
任意一个 mid，要么在左半边有序，要么在右半边有序。
判断哪边有序，然后看 target 在不在有序的那边。
图解：
旋转点
↓
[4, 5, 6, 7] [0, 1, 2]
↑ ↑
最小值 最大值
判断 mid 在哪边：
- 如果 nums[left] <= nums[mid]，左半边有序
- 否则，右半边有序
4.2 寻找峰值（LeetCode 162）
考察点：二分的条件判断
问题：找峰值，峰值定义是比邻居大
nums = [1, 2, 3, 1]，峰值可以是 2 或 3
关键洞察：
- 如果 nums[mid] < nums[mid+1]，那么右边一定有一个峰值
- 因为数组边界是负无穷！
为什么？
1 2 3 1
↑
mid=2, nums[mid]=3
nums[mid+1]=1 < 3
所以左边可能有峰值（3 本身）
但如果 nums[mid] < nums[mid+1]：
1 2 3 1
↑
mid=1, nums[mid]=2
nums[mid+1]=3 > 2
右边一定有一个峰值！
因为如果右边没有峰值，就一直升...
五、面试高频追问
| 追问 | 考察点 | 回答要点 |
|---|---|---|
| 二分查找为什么是 O(log n)？ | 复杂度分析 | 每次排除一半 |
| left <= right 还是 left < right？ | 边界条件 | 通常 <=，取决于场景 |
| mid = (left+right)/2 有什么问题？ | 整数溢出 | 用 left + (right-left)/2 |
| 找不到时返回什么？ | 边界处理 | 通常返回 -1 或插入位置 |
| 旋转数组怎么二分？ | 变形应用 | 判断哪边有序 |
六、面试总结
二分查找的本质
┌─────────────────────────────────────────────────┐
│ 二分查找的本质 │
├─────────────────────────────────────────────────┤
│ │
│ 核心思想：每次排除一半 │
│ │
│ 为什么快：log₂(n) 次就能找到 │
│ │
│ 适用条件：有序 + 可随机访问 │
│ │
│ 关键点：边界条件处理 │
│ │
│ 变体：左边界、右边界、插入位置 │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释为什么是 O(log n)
"每次排除一半，k 次后搜索空间是 n/2^k，
令 n/2^k=1，得 k=log₂(n)"
2. 能正确处理边界
"left <= right 还是 < 取决于是否包含 right"
3. 能处理变形题
"旋转数组的关键是判断哪边有序"
4. 能写没有 bug 的代码
"mid = left + (right - left) // 2 防止溢出"
相关题目
- LeetCode 33 - 搜索旋转排序数组 - 二分变形
- LeetCode 162 - 寻找峰值 - 二分应用
- LeetCode 34 - 在排序数组中查找元素的第一和最后位置 - 左右边界