02.5.1.1 二分模板与边界
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找
02.5.1.1-001 二分查找的前提是什么?
一句话结论
二分要求搜索空间满足单调性:按候选解排列后,判定结果一侧可行、一侧不可行;有序数组是最常见形态;无单调性不能用二分。
概念解释
- 单调:比较后可排除一半区间。
- 有序:元素按大小排列。
- 候选解:数组下标或答案区间。
原理流程
- 确认区间单调。
- 取中点判定。
- 排除不可能的一半。
代码 / 图示
有序:[1,3,5,7,9],target=5
中点排除一半
常见误区
- 误区:无序数组也能二分;正解:必须有序或判定函数单调。
- 误区:二分只适用于数组;正解:答案空间单调即可二分答案。
追问
- Q:部分有序能用二分吗? A:旋转数组等可分段判定,见 02.5.1.2。
- Q:二分为什么快? A:每次折半 O(log n)。
02.5.1.1-002 基本二分查找(LC 704)怎么写?
一句话结论
左闭右闭区间 [l, r],中点比较 target,相等返回下标;target 小则右界收缩,大则左界收缩;O(log n) 时间 O(1) 空间。
概念解释
- 区间含两端。
- 中点比较。
- 收缩一侧。
原理流程
l=0, r=n-1。mid比较。- 命中返回,否则收缩。
代码 / 示例
public int search(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
常见误区
- 误区:循环条件
l < r配l<=r口径;正解:区间定义与循环条件一致。 - 误区:边界更新不排除 mid;正解:命中已返回,另一侧
±1。
追问
- Q:找不到返回什么? A:按题意 -1 或插入位置。
- Q:重复元素返回哪个? A:本模板返回任意一个,需最左/最右用边界模板。
02.5.1.1-003 左闭右闭与左闭右开怎么选?
一句话结论
左闭右闭 [l,r] 循环 l<=r,更新 l=mid+1、r=mid-1;左闭右开 [l,r) 循环 l<r,更新 l=mid+1、r=mid;统一一种口径可减少死循环。
概念解释
- 区间定义。
- 循环条件。
- 边界更新配套。
原理流程
- 选定区间口径。
- 循环条件配套。
- 更新不遗漏不重复。
代码 / 图示
闭:[l, r],while l<=r
开:[l, r),while l<r
常见误区
- 误区:闭区间用
r=mid;正解:闭区间排除 mid 用r=mid-1。 - 误区:开区间用
r=n-1;正解:开区间右界为 n。
追问
- Q:面试推荐哪种? A:左闭右开写边界查找更顺,见 02.5.1.1-004。
- Q:两种能混用吗? A:能,但必须配套,混写易死循环。
02.5.1.1-004 lower_bound(第一个 ≥ target)怎么写?
一句话结论
左闭右开,a[mid] < target 则左界右移,否则右界收缩到 mid;结束时 l 即第一个 ≥ target 的位置,可能等于 n;O(log n)。
概念解释
- 下界:首个不小于目标。
- 收缩保留候选。
- 返回插入位置。
原理流程
l=0, r=n。a[mid]<target排除左半。- 否则右界留 mid。
代码 / 示例
int lowerBound(int[] a, int target) {
int l = 0, r = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
常见误区
- 误区:
a[mid] <= target才右移;正解:>=即候选,r=mid。 - 误区:返回
l-1;正解:lower_bound 返回 l 本身。
追问
- Q:target 大于所有元素? A:返回 n,需越界判断。
- Q:Java Arrays.binarySearch 行为? A:未找到返回
-(插入位置)-1。
02.5.1.1-005 upper_bound(第一个 > target)怎么写?
一句话结论
a[mid] <= target 左界右移,否则右界收缩;结束 l 为第一个 > target 的位置;upper_bound - lower_bound 即 target 出现次数;O(log n)。
概念解释
- 上界:首个大于目标。
- 等于归入左侧。
- 区间计数。
原理流程
l=0, r=n。a[mid]<=target排除左半。- 否则右界留 mid。
代码 / 示例
int upperBound(int[] a, int target) {
int l = 0, r = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] <= target) l = mid + 1;
else r = mid;
}
return l;
}
常见误区
- 误区:upper_bound 找最后一个 ≤;正解:那是
upper_bound-1。 - 误区:等于时收缩右界;正解:等于归入左侧继续右移。
追问
- Q:区间
[lower, upper)含义? A:所有等于 target 的元素。 - Q:target 小于所有? A:返回 0。
02.5.1.1-006 最后一个 ≤ target / < target 怎么求?
一句话结论
最后一个 ≤ target 即 upper_bound(target) - 1;最后一个 < target 即 lower_bound(target) - 1;找不到返回 -1;复用上下界模板。
概念解释
- 反向位置。
- 上下界偏移。
- 越界返回 -1。
原理流程
- 求对应上/下界。
- 减一。
- 判 -1。
代码 / 示例
int lastLe(int[] a, int target) {
int idx = upperBound(a, target) - 1;
return idx >= 0 ? idx : -1;
}
常见误区
- 误区:直接写反向二分易死循环;正解:复用上下界减一。
- 误区:减一后未判负;正解:target 过小返回 -1。
追问
- Q:最后一个等于 target? A:
upper_bound-1,再校验值相等。 - Q:首末位置查找? A:lower_bound 与 upper_bound-1。
02.5.1.1-007 二分怎么避免死循环?
一句话结论
每次收缩必须排除 mid:闭区间 ±1,开区间 l=mid+1 或 r=mid;循环条件与区间口径一致;mid 取偏左((l+r)>>>1),避免 l=mid 时两数相邻卡死。
概念解释
- 排除 mid。
- 口径一致。
- 中点偏左。
原理流程
- 检查更新是否缩小区间。
- 相邻两数 mid 落点。
- 循环终止条件。
代码 / 图示
相邻 l,r:mid=l
若 l=mid 且 r 不动 → 死循环
常见误区
- 误区:
r=mid配闭区间;正解:口径配套。 - 误区:
mid=(l+r)/2相邻时偏右;正解:整数除法偏左,配合更新方向。
追问
- Q:什么更新会卡死? A:
l=mid而 mid 恒等于 l。 - Q:调试死循环看什么? A:区间长度是否每轮严格减小。
02.5.1.1-008 mid 下标为什么要防溢出?
一句话结论
(l+r)/2 在两数接近整型上限时相加溢出;用 l + (r-l)/2 或无符号右移 (l+r)>>>1;结果等价且不溢出。
概念解释
- 相加溢出。
- 差值非负。
- 无符号右移。
原理流程
- 避免先加。
- 差值折半。
- 加回左界。
代码 / 示例
int mid = l + (r - l) / 2;
// 或 int mid = (l + r) >>> 1;
常见误区
- 误区:数组下标不会溢出;正解:大下标相加仍可能越 int 范围。
- 误区:
>>>与>>混用;正解:非负下标用>>>无符号右移。
追问
- Q:long 范围? A:差值用 long 防溢出。
- Q:mid 偏左还是偏右? A:整数除法向下取整偏左。
02.5.1.1-009 二分查找复杂度怎么算?
一句话结论
每轮区间减半,比较次数 ⌈log₂ n⌉,时间 O(log n);额外空间 O(1);递归二分栈 O(log n);优于线性 O(n),但要求有序或单调。
概念解释
- 折半次数。
- 常数比较。
- 辅助空间。
原理流程
- 区间规模 n。
- 每轮减半。
- 到 1 为止 O(log n)。
代码 / 图示
n → n/2 → n/4 → … → 1
轮数 log₂ n
常见误区
- 误区:二分 O(log n) 但排序免费;正解:有序性需预先排序 O(n log n)。
- 误区:递归二分空间 O(1);正解:递归栈 O(log n)。
追问
- Q:无序但查多次? A:先排序 O(n log n),后续每次 O(log n)。
- Q:二分最坏比较次数? A:⌈log₂(n+1)⌉ 量级。
02.5.1.1-010 搜索插入位置(LC 35)怎么做?
一句话结论
target 存在返回下标,不存在返回插入后位置;即 lower_bound 模板;O(log n);位置范围 [0, n]。
概念解释
- 下界即插入点。
- 存在与否同一模板。
- 末尾插入合法。
原理流程
- lower_bound 求位置。
- 位置在区间内校验值相等。
- 返回位置。
代码 / 示例
public int searchInsert(int[] a, int target) {
int l = 0, r = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
常见误区
- 误区:target 大于全部返回 n-1;正解:返回 n。
- 误区:找不到额外线性查找;正解:下界位置即插入点。
追问
- Q:重复元素插哪里? A:插在首个等于 target 之前。
- Q:空数组? A:返回 0。
02.5.1.1-011 平方根(LC 69)为什么用二分?
一句话结论
整数平方根满足 x² ≤ n 且单调,二分答案找最大 x;x 从 0 到 n;O(log n);避免浮点精度问题。
概念解释
- 答案单调。
- 判定
x²≤n。 - 最大可行值。
原理流程
- 答案区间二分。
- 中点平方判定。
- 收缩找最大满足。
代码 / 示例
public int mySqrt(int n) {
long l = 0, r = n, ans = 0;
while (l <= r) {
long mid = (l + r) / 2;
if (mid * mid <= n) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
return (int) ans;
}
常见误区
- 误区:mid*mid int 溢出;正解:用 long 或
mid <= n/mid。 - 误区:取最接近而非向下取整;正解:题目要求整数部分。
追问
- Q:浮点平方根? A:二分区间缩到精度,或调用库函数。
- Q:这属于哪类二分? A:二分答案,见 02.5.1.3。
02.5.1.1-012 含重复元素时二分怎么定位?
一句话结论
找最左 target 用 lower_bound 再校验;找最右 target 用 upper_bound-1 再校验;普通等值二分只返回任意一个;重复不影响 O(log n)。
概念解释
- 最左:下界。
- 最右:上界偏移。
- 校验存在。
原理流程
- 求下界/上界。
- 校验值相等。
- 返回位置或 -1。
代码 / 示例
int left = lowerBound(a, target);
if (left == a.length || a[left] != target) return -1;
int right = upperBound(a, target) - 1;
常见误区
- 误区:重复时返回位置不稳定被判错;正解:按题意要最左/最右。
- 误区:上界减一后未校验;正解:可能不存在 target。
追问
- Q:target 出现次数? A:
upper-lower。 - Q:重复元素区间? A:
[lower, upper)。
02.5.1.1-013 局部最小值为什么可以二分?
一句话结论
若两端已知大小关系且相邻值有单调性倾向,局部最小可通过中点与邻居比较排除一侧;数组不必全局有序,只要比较后能确定最小值所在侧。
概念解释
- 局部:比邻居小。
- 比较排除。
- 非全局有序。
原理流程
- 中点与左/右邻居比。
- 哪侧下降哪侧可能有极小。
- 收缩区间。
代码 / 图示
a[mid] > a[mid-1] → 左侧可能有谷
常见误区
- 误区:局部问题必须全局有序;正解:比较后能排除一半即可。
- 误区:只比较中点不看邻居;正解:局部性质需邻居参照。
追问
- Q:LC 162 峰值元素? A:对称思路,比较高处侧。
- Q:存在多个局部最小? A:返回任意一个即可。
02.5.1.1-014 二分有哪些边界用例?
一句话结论
空数组、单元素、target 在首尾、target 越界两侧、全部相等、相邻两元素、旋转退化;判空、返回位置越界与口径校验。
概念解释
- 空与最短。
- 端点与越界。
- 等值退化。
原理流程
- 空数组返回约定。
- 单元素直接比较。
- 端点与越界检查。
代码 / 图示
[] / [1]
target<a[0] / target>a[n-1]
全相等 / 两元素
常见误区
- 误区:空数组访问 a[0];正解:先判长度。
- 误区:插入位置越界未处理;正解:允许返回 n。
追问
- Q:全相等数组 lower_bound? A:返回 0。
- Q:两元素死循环? A:检查 mid 落点与更新方向。
02.5.1.1-015 二分时不变量是什么?
一句话结论
不变量:答案始终落在当前区间内;每轮收缩后保留可能包含答案的一侧;结束时区间边界即答案位置;写模板先固定不变量再写更新。
概念解释
- 区间不变量。
- 候选保留。
- 终止即答案。
原理流程
- 写出区间含义。
- 比较后保留含答案侧。
- 区间收敛到答案。
代码 / 图示
[lo, hi) 内存在答案
更新后不变量仍成立
常见误区
- 误区:更新后答案被排除;正解:按判定方向保留候选侧。
- 误区:不变量前后口径不一致;正解:闭/开区间写清。
追问
- Q:怎么自检不变量? A:每轮标注区间代表的候选集合。
- Q:终止条件对应什么? A:候选区间只剩一个位置。
02.5.1.1-016 常见死循环由什么造成?
一句话结论
区间口径与循环条件不符、更新边界未排除 mid、相邻两数时 l=mid 或 r=mid 不推进;逐轮检查区间长度是否严格减小。
概念解释
- 口径错配。
- 未排除 mid。
- 相邻卡死。
原理流程
- 核对循环条件。
- 核对更新 ±1 还是留 mid。
- 相邻两数模拟。
代码 / 图示
l=mid, mid=l → l 不变
常见误区
- 误区:把死循环归为代码笔误;正解:多为区间口径错配。
- 误区:加大循环上限解决;正解:修正收缩方向。
追问
- Q:闭区间
l<=r配r=mid? A:mid 被保留,相邻时卡死。 - Q:怎么模拟调试? A:打印每轮 l, mid, r。
02.5.1.1-017 二分与线性查找怎么对比?
一句话结论
线性 O(n) 不要求有序;二分 O(log n) 要求有序或单调,且需随机访问;有序静态数据集二分优势明显;频繁插入数据结构另议。
概念解释
- 前提条件。
- 访问方式。
- 成本对比。
原理流程
- 看是否有序。
- 看能否随机访问。
- 比较 O(n) 与 O(log n)。
代码 / 图示
无序:线性 O(n)
有序静态:二分 O(log n)
常见误区
- 误区:二分总比线性快;正解:无序不能二分。
- 误区:链表上二分;正解:链表不支持 O(1) 随机访问。
追问
- Q:有序链表能二分吗? A:不能高效随机访问,只能线性。
- Q:预排序成本? A:n 次查询才摊薄排序 O(n log n)。
02.5.1.1-018 二分模板怎么选型?
一句话结论
找等值用基本模板;找首末/插入位置用 lower/upper_bound;答案单调用二分答案;先判定属于哪类,再选对应模板,不要混合口径。
概念解释
- 等值查找。
- 边界定位。
- 答案二分。
原理流程
- 明确返回含义。
- 选模板。
- 固定区间口径。
代码 / 图示
命中下标:基本
首末/插入:上下界
可行值:二分答案
常见误区
- 误区:一套模板套所有变体;正解:返回值决定模板。
- 误区:边界题用等值模板;正解:需保留候选侧。
追问
- Q:最大值最小化? A:二分答案,见 02.5.1.3。
- Q:二维有序矩阵? A:见 02.5.1.4。
02.5.1.1-019 二分复杂度怎么汇报?
一句话结论
时间 O(log n),空间 O(1) 迭代 / O(log n) 递归;预处理有序性另计排序 O(n log n);二分答案轮次取决于答案范围对数,判定代价另乘。
概念解释
- 折半对数。
- 辅助空间。
- 判定代价。
原理流程
- 标注候选规模 n。
- 每轮判定 O(1) 或 O(k)。
- 分列时间空间。
代码 / 图示
数组二分:O(log n) / O(1)
二分答案:O(log R · check(mid))
常见误区
- 误区:二分答案只报 O(log n);正解:乘 check 复杂度。
- 误区:递归不计栈;正解:O(log n) 栈。
追问
- Q:答案范围 R 很大? A:log R 轮,与 n 无关。
- Q:判定 O(n) 的二分答案? A:整体 O(n log R)。
02.5.1.1-020 二分模板常见变体有哪些?
一句话结论
等值查找、lower/upper_bound、插入位置、整数平方根、局部峰谷、旋转数组分段判定、二分答案、二维矩阵;主线是区间不变量 + 收缩方向。
概念解释
- 框架:折半收缩。
- 变体:判定函数不同。
- 场景包装。
原理流程
- 固定区间口径。
- 写判定条件。
- 保留候选侧。
代码 / 图示
判定 → 收缩 → 收敛
常见误区
- 误区:变体题重新发明模板;正解:复用区间不变量。
- 误区:判定方向写反导致答案错位;正解:用样例验证收缩方向。
追问
- Q:旋转数组见哪页? A:02.5.1.2。
- Q:二分答案见哪页? A:02.5.1.3。