二分查找
从 LC 35 出发，看暴力线性扫为什么不够，再把二分归约到一份模板上。
1. 核心原理
二分查找（binary search）解决的问题形式固定：在一个有序的对象（数组、值域、统计量）上，找一个满足某种单调条件的位置或值。每一步把候选区间砍掉一半，整体复杂度从线性 O(n) 降到对数 O(log n)。
题面会有多种伪装——"找下标"、"找最小满足"、"找第 K 个"——但代码骨架只有一种：搜索区间 [left, right) + 循环 while left < right + 一个单调的判定函数。掌握这三件套之后，所有变体都靠改写判定函数解决。
暴力线性扫为什么不够
最直觉的写法是从左到右挨个比较，时间 O(n)。在 n ≤ 10⁴ 的数据范围里能 AC，但题目一旦把范围放大到 10⁹（典型如"在某个值域里找最小可行答案"），线性扫直接 TLE。数组本身已经有序，这个结构线性扫一点没用上——正是二分能切入的地方。
算法的关键洞察
有序数组的本质是：任意位置 i 处的元素和 target 之间的大小关系，决定了 i 的左侧或右侧整片元素相对 target 的位置也确定。具体说，若 nums[mid] >= target，则 mid 右边所有元素也都 >= target；若 nums[mid] < target，则 mid 左边所有元素都 < target。
整段数组被划分为两片：左边一片 < target，右边一片 >= target，中间夹着一条翻转边界。二分要找的就是这条边界——即第一个 True 的下标。
每查一次 nums[mid]，要么把"左边一定 < target"的范围扩大，要么把"右边一定 >= target"的范围扩大。两片确定区域向中间逼，每次砍掉一半未确定区间——这就是 O(log n) 的来源。
抽象成一句话：
二分要的就是一个单调的判定函数
check(i)——check返回True的下标构成一段后缀，返回False的下标构成一段前缀。二分找的就是第一个True的下标。
这种"找第一个 True"的形态在 C++ 标准库里有个标准名字叫 lower_bound。它是这一族所有二分变体的母模板。
套路类型一览
下标二分有四种常见变体，本质都是 lower_bound 的改写：
| 想找的位置 | check 函数 | 转化方式 |
|---|---|---|
第一个 ≥ target | nums[i] >= target | lower_bound(target) |
第一个 > target | nums[i] > target | lower_bound(target + 1)（整数） |
最后一个 ≤ target | 第一个 > target − 1 | lower_bound(target + 1) - 1 |
最后一个 < target | 第一个 ≥ target − 1 | lower_bound(target) - 1 |
四种变体全部归约到 lower_bound 一份模板，写代码时不再纠结 < / <=，只需把题目问的东西翻译成"第一个 ≥ X 是哪"。
本章从 LC 35 出发立模板，下一章 二分答案 把同一份模板搬到答案值域上，第三章 第 K 小 再搬到统计量上。三章共享同一个外壳，差异都在判定函数。
2. 通用模板
下面给出左闭右开 [l, r) 风格的 lower_bound 母模板：返回数组里第一个 nums[i] >= target 的下标 i，若不存在则返回 len(nums)。这种区间风格的好处是终止条件只有一种 l == r，循环里也不需要"再多查一次 mid"。
def lower_bound(nums: list[int], target: int) -> int:
"""
返回第一个 nums[i] >= target 的下标 i；
若所有元素都 < target，返回 len(nums)。
搜索区间维护为左闭右开 [l, r)。
"""
l, r = 0, len(nums) # 注意 r = n，不是 n - 1
while l < r:
mid = (l + r) // 2 # Python 整数无溢出
if nums[mid] >= target:
r = mid # mid 可能就是答案，把右边收到 mid（不 -1）
else:
l = mid + 1 # mid 已确定 < target，向右移
return l # l == r，即翻转边界int lowerBound(int[] nums, int target) {
int l = 0, r = nums.length; // 左闭右开 [l, r)
while (l < r) {
int mid = l + (r - l) / 2; // 防溢出写法，等价 (l + r) / 2
if (nums[mid] >= target) {
r = mid; // mid 可能是答案
} else {
l = mid + 1; // 排除 mid
}
}
return l;
}int lowerBound(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size(); // 左闭右开 [l, r)
while (l < r) {
int mid = l + (r - l) / 2; // 防溢出写法
if (nums[mid] >= target) {
r = mid; // mid 可能是答案
} else {
l = mid + 1; // 排除 mid
}
}
return l;
}模板的四个循环不变量盯死了，二分就立得住：
- 区间
[l, r)始终是"还没确定"的下标范围；[0, l)全部< target，[r, n)全部≥ target。 mid = l + (r - l) / 2永远在[l, r)内（向下取整），且每轮区间长度至少砍一半。- 收缩规则：
nums[mid]满足条件时r = mid（保留 mid 候选），否则l = mid + 1（排除 mid）。 - 终止条件
l == r时区间空，l就是分界点；不存在时l == n，模板对空数组也自动正确。
后续所有二分题，只要把 nums[mid] >= target 换成对应的 check(mid)，骨架完全不动。
闭区间 [l, r] 也是一种自洽风格（r = n - 1 / while l <= r / r = mid - 1），两套不要混用——本章默认左闭右开。
3. 母题精讲
二分查找是这本书里第一个"套路远多于代码"的算法。题面千变万化——找下标、找最小满足、找第 K 个——但模板就一份。下面从 LC 35 出发立模板。
LeetCode 35. 搜索插入位置
链接：LeetCode 35
题意：给一个升序排列且不含重复元素的整数数组 nums，再给一个目标值 target。如果 target 在数组里，返回它的下标；如果不在，返回它按顺序插入后所处的下标。要求 O(log n)。
数据范围：
nums.length：1 到 10⁴nums[i]：−10⁴ 到 10⁴，严格升序target：−10⁴ 到 10⁴
示例：
输入：nums = [1, 3, 5, 6], target = 5
输出：2
输入：nums = [1, 3, 5, 6], target = 2
输出：1
输入：nums = [1, 3, 5, 6], target = 7
输出：4先用暴力解打个底
说白了，最直接的写法就是一次循环——从左到右扫，找到第一个 nums[i] >= target 的位置，就是答案：
class Solution:
def searchInsert_brute(self, nums: list[int], target: int) -> int:
for i, x in enumerate(nums):
if x >= target:
return i
return len(nums)时间 O(n)，空间 O(1)。功能完全正确——n ≤ 10⁴ 下能 AC。
为什么不能就这么交？两个问题：
一是题目明确写了 O(log n)，线性扫一上来就违约。
二是把数据范围放大就崩——n 提到 10⁹（比如题目改成"在 [0, 10⁹) 区间找一个满足某条件的最小整数"）线性扫直接 TLE，得把 n 砍成 log n。
数组本身已经升序，这个结构暴力解一点没用上——从这里下手。
把单调性掰开看：为什么能二分
数组升序的本质，是：nums[mid] >= target 时 mid 右边一整片也都 ≥ target；反过来 nums[mid] < target 时 mid 左边一整片都 < target。
换句话说，整个数组被劈成两半：左边一片 < target（蓝色），右边一片 >= target（红色），中间夹着一条边界。要找的就是这条边界——红色区域里最左的那个下标。
你看，每查一次 nums[mid]，要么把"左边一定蓝"的范围扩大，要么把"右边一定红"的范围扩大。两条染色边像左右夹击一样向中间逼，每次砍掉一半未染色区间——这就是 O(log n) 的来源。
一句话：单调性是判定函数的"骨头"，没有单调性二分就立不住。
下面这个交互演示走一遍 lower_bound([1, 2, 4, 5, 5, 7, 8], target=5) 的过程：
lower_bound([1, 2, 4, 5, 5, 7, 8], target=5)
红蓝染色：左边一定 < target（蓝），右边一定 ≥ target（红）
总共三次访问，每次砍掉一半区间，log₂(7) ≈ 3 次内收敛——这就是 O(log n) 的样子。
4. 三道例题练手
下面三道按"判定函数怎么造"由易到难排：直接 ≥（LC 35）、调两次 ≥（LC 34）、局部单调（LC 33）。三道题的二分外壳完全一样，差异都在判定函数上。
4.1 LC 35 搜索插入位置
链接：LeetCode 35
题意：给一个升序排列且不含重复元素的整数数组 nums，再给一个目标值 target。如果 target 在数组里，返回它的下标；如果不在，返回它按顺序插入后所处的下标。要求 O(log n)。
数据范围：nums.length 1 到 10⁴，nums[i] 和 target ±10⁴，严格升序。
示例：
输入：nums = [1, 3, 5, 6], target = 5 → 2
输入：nums = [1, 3, 5, 6], target = 2 → 1
输入：nums = [1, 3, 5, 6], target = 7 → 4回到本章开头那道题。本质就是 lower_bound(nums, target)——找第一个 >= target 的下标。target 存在就是它本身，不存在就是它该插入的位置；全部 < target 时返回 len(nums) 也正好对应"插到末尾"。一份模板搞定所有 case。
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
l, r = 0, len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return lclass Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
}class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};复杂度 O(log n)、空间 O(1)。
Follow-up：如果数组允许重复呢——找的不是"插入位置"而是"target 第一次出现和最后一次出现"两个下标？
4.2 LC 34 在排序数组中查找元素的第一个和最后一个位置
链接：LeetCode 34
题意：给一个升序排列的整数数组 nums（可以有重复），和一个目标值 target。返回长度为 2 的数组 [first, last]——target 在 nums 中第一次出现和最后一次出现的下标。如果 target 不在 nums 中，返回 [-1, -1]。要求 O(log n)。
数据范围：
nums.length：0 到 10⁵nums[i]：−10⁹ 到 10⁹target：−10⁹ 到 10⁹
示例：
输入：nums = [5, 7, 7, 8, 8, 10], target = 8
输出：[3, 4]
输入：nums = [5, 7, 7, 8, 8, 10], target = 6
输出：[-1, -1]
输入：nums = [], target = 0
输出：[-1, -1]套路就一招：两次 lower_bound，问题解决：
first = lower_bound(target)——第一个>= target的下标，如果它正好等于target就是答案。last = lower_bound(target + 1) - 1——第一个> target的下标减一，正好是最后一个== target的下标。
lower_bound(target + 1) - 1 这个转换值得记一下——本质上就是把 > 借给 >= 解决，整数情况下完全等价。这一类转化在二分里反复出现：模板只有一个，剩下的都靠"翻译"。
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
def lower_bound(t: int) -> int:
l, r = 0, len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= t:
r = mid
else:
l = mid + 1
return l
first = lower_bound(target)
if first == len(nums) or nums[first] != target:
return [-1, -1] # target 根本不在
last = lower_bound(target + 1) - 1
return [first, last]class Solution {
public int[] searchRange(int[] nums, int target) {
int first = lowerBound(nums, target);
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
}
int last = lowerBound(nums, target + 1) - 1;
return new int[]{first, last};
}
private int lowerBound(int[] nums, int t) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= t) r = mid;
else l = mid + 1;
}
return l;
}
}class Solution {
int lowerBound(vector<int>& nums, int t) {
int l = 0, r = (int)nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= t) r = mid;
else l = mid + 1;
}
return l;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int first = lowerBound(nums, target);
if (first == (int)nums.size() || nums[first] != target) {
return {-1, -1}; // target 根本不在
}
int last = lowerBound(nums, target + 1) - 1;
return {first, last};
}
};复杂度 O(log n)、空间 O(1)。
这里有个坑：lower_bound(target + 1) 在题面允许 target == INT_MAX 时会溢出。LC 34 里 target ≤ 10⁹，加一还在 int 范围，没问题。要是题目真把 target 塞到 INT_MAX，就把 target + 1 换成 target 上的"找最后一个 ≤ target"——同样的套路，转化形式略变。
Follow-up：上面两题数组都是全局升序。如果数组被"旋转过"一次——比如 [4, 5, 6, 7, 0, 1, 2]——还能二分吗？
4.3 LC 33 搜索旋转排序数组
链接：LeetCode 33
题意：给一个原本升序、值都互不相同的数组 nums，但它在某个未知下标处被"旋转"了一次（前面一段挪到末尾）。比如 [0, 1, 2, 4, 5, 6, 7] 可能变成 [4, 5, 6, 7, 0, 1, 2]。给一个 target，返回它在 nums 中的下标；不存在返回 −1。要求 O(log n)。
数据范围：
nums.length：1 到 5000nums[i]：−10⁴ 到 10⁴，互不相同target：−10⁴ 到 10⁴
示例：
输入：nums = [4, 5, 6, 7, 0, 1, 2], target = 0
输出：4
输入：nums = [4, 5, 6, 7, 0, 1, 2], target = 3
输出：-1整个数组不再单调，看着没法二分。但其实有个关键性质：任何一段 [l, mid] 和 [mid, r] 中至少有一段是单调升序的——因为只旋转一次，旋转点只可能落在一段里。
套路就出来了——每轮二分，先判"哪一半有序"：
- 如果
nums[l] <= nums[mid]，左半[l, mid]是有序的； - 否则右半
[mid, r-1]是有序的。
然后看 target 是不是落在那一半有序区间里——落在就走有序的那半（继续二分），不落在就走另一半。每轮砍掉一半，整体 O(log n)。
本质上还是二分，只是判定函数从"单点比较"变成了"先判哪段单调再判落点"。模板没变。
下面这个交互演示走一遍 [4, 5, 6, 7, 0, 1, 2] 找 target=0 的过程：
search([4, 5, 6, 7, 0, 1, 2], target=0)
先判断哪一半单调，再判 target 落在哪半
代码（这里用闭区间 [l, r] 写，因为"mid == target 时直接返回"更顺）：
class Solution:
def search(self, nums: list[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # 左半 [l, mid] 有序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # 右半 [mid, r] 有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
}class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半 [l, mid] 有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半 [mid, r] 有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
};复杂度 O(log n)、空间 O(1)。
两个容易踩坑的点：
一是"左半有序" 判定要用 nums[l] <= nums[mid] 而不是 <——当 l == mid 时（区间只剩两个元素），左半就是 [l, l]，长度 1 必然有序。漏了等号会丢这种 case。
二是 target 判定的区间端点要包含 nums[l]、nums[r]，但要排除 nums[mid]（因为 nums[mid] != target 已检查过）。所以条件写 nums[l] <= target < nums[mid]，不是 < nums[l] 或 <= nums[mid]。
这套思路其实是可以推广的——只要数组有"局部单调"的结构（旋转、山峰、波形），都能用"先判哪段单调，再判 target 落点"的套路二分。LC 81（含重复元素的旋转）、LC 153（找旋转点）、LC 162（找峰值）都是这一族。换句话说，框架不变，判定函数换换。
5. 边界与易错（八个坑）
这一族常踩的八个坑全收在这里。看完这八条，二分的细节坑基本就清完了。
1. mid 溢出
mid = (l + r) / 2 在 C/Java/Go 里当 l + r > INT_MAX 时会溢出。标准写法是 mid = l + (r - l) / 2——等价但避免溢出。Python 整数无溢出问题，但跨语言移植时统一写后者更稳。
2. 死循环：为什么 l = mid 一定要小心
闭区间 [l, r] 写法里，如果 l = mid 而 mid 又等于 l，下一轮 l 还是同一个值——无限循环。规避办法就一个：左闭右开 [l, r) 模板配 l = mid + 1、r = mid，永远不会卡住。
闭区间也有同样的陷阱——闭区间下要用 l = mid + 1，不要写成 l = mid。
3. 空数组
nums = [] 时 len(nums) = 0，l = 0, r = 0，循环 l < r 不进，直接返回 l = 0——lower_bound 模板自动正确处理。但 LC 33 这种闭区间写 r = nums.length - 1 = -1，l = 0 > r = -1，循环也不进，返回 -1，也正确。模板对空数组都有正确兜底。
4. 重复元素
LC 35 题面保证不重复，LC 34 题面允许重复。lower_bound 处理重复时返回最左的位置（即 nums[i] >= target 的最左），这正是"第一次出现"。如果题面允许重复元素且某些题要求"任意位置"（不是第一次），仍然用 lower_bound，然后判一下 nums[i] == target。
5. 值域上下界
不是所有题都在数组下标上二分。下一章 二分答案 会在答案值域上二分，第三章在统计量上二分。值域范围要包含真实答案——上下界给错会直接出错。
整数二分上界一般取"最大可能答案 + 1"（左闭右开），下界取"最小可能答案"。
6. 判定函数必须单调
这是最隐蔽的一条——判定函数一旦不单调，二分直接死。LC 35 / 34 里 check 就是数组本身的升序，天然单调；LC 33 是局部段单调，靠"先判哪段有序"绕过。
下一章会大段讨论"怎么把题目里的判定函数翻译成单调"——二分答案这一族的精华几乎全在这一步。框架是死的，单调性是活的。
7. 区间风格不要混用
左闭右开 [l, r) 和闭区间 [l, r] 是两套自洽的风格：
| 风格 | 初值 | 循环 | 缩区间 |
|---|---|---|---|
[l, r) | r = n | while l < r | l = mid + 1 / r = mid |
[l, r] | r = n - 1 | while l <= r | l = mid + 1 / r = mid - 1 |
一个文件里只用一种，混着写迟早卡死循环。本章模板用 [l, r)，旋转数组那道因为"== 时立即返回"用 [l, r]——两套各自闭环，不要拼起来。
8. 浮点二分兜底
LC 35 / 34 / 33 都是整数二分。但浮点版本（比如 LC 644 平均值二分、LC 786 分数二分）有精度陷阱——while hi - lo > eps 在累积误差下可能不收敛。标准做法是固定 100 次迭代，覆盖 2¹⁰⁰ 倍精度收缩，远超 IEEE 754 双精度尾数的需求。
复杂度速查
| 题 | 时间 | 空间 |
|---|---|---|
| LC 35 搜索插入位置 | O(log n) | O(1) |
| LC 34 第一个和最后一个位置 | O(log n) | O(1) |
| LC 33 旋转数组搜索 | O(log n) | O(1) |
7. 小结
一句话收尾：二分查找的本质是"找单调判定的边界"。把 lower_bound 那份模板写熟，剩下的变体（>、<=、<）都能用 target ± 1 或减一转化。
再喊一遍那句口号——二分模板就一个：搜索区间 [left, right) + while left < right + 看判定函数。
下一章 二分答案 把这套模板搬到答案的值域上——题目不会直接告诉你哪里有序，但只要能写出一个关于"候选答案 x"单调的 check(x)，就能在值域上二分。框架不变，只换判定函数。
对应灵神题单：二分查找基础 / 二分变体
进一步阅读：灵茶山艾府《二分算法题单》第一部分；LeetCode 二分查找标签