罗罗编程学习记录
本页内容 展开查看

02.5.1.1 二分模板与边界

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找

02.5.1.1-001 二分查找的前提是什么?

一句话结论

二分要求搜索空间满足单调性:按候选解排列后,判定结果一侧可行、一侧不可行;有序数组是最常见形态;无单调性不能用二分。

概念解释

  • 单调:比较后可排除一半区间。
  • 有序:元素按大小排列。
  • 候选解:数组下标或答案区间。

原理流程

  1. 确认区间单调。
  2. 取中点判定。
  3. 排除不可能的一半。

代码 / 图示

有序:[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) 空间。

概念解释

  • 区间含两端。
  • 中点比较。
  • 收缩一侧。

原理流程

  1. l=0, r=n-1。
  2. mid 比较。
  3. 命中返回,否则收缩。

代码 / 示例

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;统一一种口径可减少死循环。

概念解释

  • 区间定义。
  • 循环条件。
  • 边界更新配套。

原理流程

  1. 选定区间口径。
  2. 循环条件配套。
  3. 更新不遗漏不重复。

代码 / 图示

闭:[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)。

概念解释

  • 下界:首个不小于目标。
  • 收缩保留候选。
  • 返回插入位置。

原理流程

  1. l=0, r=n。
  2. a[mid]<target 排除左半。
  3. 否则右界留 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)。

概念解释

  • 上界:首个大于目标。
  • 等于归入左侧。
  • 区间计数。

原理流程

  1. l=0, r=n。
  2. a[mid]<=target 排除左半。
  3. 否则右界留 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. 求对应上/下界。
  2. 减一。
  3. 判 -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。
  • 口径一致。
  • 中点偏左。

原理流程

  1. 检查更新是否缩小区间。
  2. 相邻两数 mid 落点。
  3. 循环终止条件。

代码 / 图示

相邻 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;结果等价且不溢出。

概念解释

  • 相加溢出。
  • 差值非负。
  • 无符号右移。

原理流程

  1. 避免先加。
  2. 差值折半。
  3. 加回左界。

代码 / 示例

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),但要求有序或单调。

概念解释

  • 折半次数。
  • 常数比较。
  • 辅助空间。

原理流程

  1. 区间规模 n。
  2. 每轮减半。
  3. 到 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]。

概念解释

  • 下界即插入点。
  • 存在与否同一模板。
  • 末尾插入合法。

原理流程

  1. lower_bound 求位置。
  2. 位置在区间内校验值相等。
  3. 返回位置。

代码 / 示例

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。
  • 最大可行值。

原理流程

  1. 答案区间二分。
  2. 中点平方判定。
  3. 收缩找最大满足。

代码 / 示例

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. 求下界/上界。
  2. 校验值相等。
  3. 返回位置或 -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 局部最小值为什么可以二分?

一句话结论

若两端已知大小关系且相邻值有单调性倾向,局部最小可通过中点与邻居比较排除一侧;数组不必全局有序,只要比较后能确定最小值所在侧。

概念解释

  • 局部:比邻居小。
  • 比较排除。
  • 非全局有序。

原理流程

  1. 中点与左/右邻居比。
  2. 哪侧下降哪侧可能有极小。
  3. 收缩区间。

代码 / 图示

a[mid] > a[mid-1] → 左侧可能有谷

常见误区

  • 误区:局部问题必须全局有序;正解:比较后能排除一半即可。
  • 误区:只比较中点不看邻居;正解:局部性质需邻居参照。

追问

  • Q:LC 162 峰值元素? A:对称思路,比较高处侧。
  • Q:存在多个局部最小? A:返回任意一个即可。

02.5.1.1-014 二分有哪些边界用例?

一句话结论

空数组、单元素、target 在首尾、target 越界两侧、全部相等、相邻两元素、旋转退化;判空、返回位置越界与口径校验。

概念解释

  • 空与最短。
  • 端点与越界。
  • 等值退化。

原理流程

  1. 空数组返回约定。
  2. 单元素直接比较。
  3. 端点与越界检查。

代码 / 图示

[] / [1]
target<a[0] / target>a[n-1]
全相等 / 两元素

常见误区

  • 误区:空数组访问 a[0];正解:先判长度。
  • 误区:插入位置越界未处理;正解:允许返回 n。

追问

  • Q:全相等数组 lower_bound? A:返回 0。
  • Q:两元素死循环? A:检查 mid 落点与更新方向。

02.5.1.1-015 二分时不变量是什么?

一句话结论

不变量:答案始终落在当前区间内;每轮收缩后保留可能包含答案的一侧;结束时区间边界即答案位置;写模板先固定不变量再写更新。

概念解释

  • 区间不变量。
  • 候选保留。
  • 终止即答案。

原理流程

  1. 写出区间含义。
  2. 比较后保留含答案侧。
  3. 区间收敛到答案。

代码 / 图示

[lo, hi) 内存在答案
更新后不变量仍成立

常见误区

  • 误区:更新后答案被排除;正解:按判定方向保留候选侧。
  • 误区:不变量前后口径不一致;正解:闭/开区间写清。

追问

  • Q:怎么自检不变量? A:每轮标注区间代表的候选集合。
  • Q:终止条件对应什么? A:候选区间只剩一个位置。

02.5.1.1-016 常见死循环由什么造成?

一句话结论

区间口径与循环条件不符、更新边界未排除 mid、相邻两数时 l=mid 或 r=mid 不推进;逐轮检查区间长度是否严格减小。

概念解释

  • 口径错配。
  • 未排除 mid。
  • 相邻卡死。

原理流程

  1. 核对循环条件。
  2. 核对更新 ±1 还是留 mid。
  3. 相邻两数模拟。

代码 / 图示

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) 要求有序或单调,且需随机访问;有序静态数据集二分优势明显;频繁插入数据结构另议。

概念解释

  • 前提条件。
  • 访问方式。
  • 成本对比。

原理流程

  1. 看是否有序。
  2. 看能否随机访问。
  3. 比较 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;答案单调用二分答案;先判定属于哪类,再选对应模板,不要混合口径。

概念解释

  • 等值查找。
  • 边界定位。
  • 答案二分。

原理流程

  1. 明确返回含义。
  2. 选模板。
  3. 固定区间口径。

代码 / 图示

命中下标:基本
首末/插入:上下界
可行值:二分答案

常见误区

  • 误区:一套模板套所有变体;正解:返回值决定模板。
  • 误区:边界题用等值模板;正解:需保留候选侧。

追问

  • 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);二分答案轮次取决于答案范围对数,判定代价另乘。

概念解释

  • 折半对数。
  • 辅助空间。
  • 判定代价。

原理流程

  1. 标注候选规模 n。
  2. 每轮判定 O(1) 或 O(k)。
  3. 分列时间空间。

代码 / 图示

数组二分: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、插入位置、整数平方根、局部峰谷、旋转数组分段判定、二分答案、二维矩阵;主线是区间不变量 + 收缩方向。

概念解释

  • 框架:折半收缩。
  • 变体:判定函数不同。
  • 场景包装。

原理流程

  1. 固定区间口径。
  2. 写判定条件。
  3. 保留候选侧。

代码 / 图示

判定 → 收缩 → 收敛

常见误区

  • 误区:变体题重新发明模板;正解:复用区间不变量。
  • 误区:判定方向写反导致答案错位;正解:用样例验证收缩方向。

追问

  • Q:旋转数组见哪页? A:02.5.1.2。
  • Q:二分答案见哪页? A:02.5.1.3。