二分查找
二分查找用单调判断反复缩小范围。本文负责半开区间、重复值边界与答案二分。
1. 面试核心
先记住这几条，再读正文- 单调性。 二分要求判断结果分成连续两段。利用这个单调边界，每次排除一半候选，并保持答案仍在剩余区间内。
- 左边界。 lower bound 返回首个大于等于目标的位置。遇到相等值仍需向左收缩，才能找到重复值的起点。卡 · 半开区间不变量
- 右边界与频次。 upper bound 返回首个大于目标的位置，两边界之差是频次。卡 · 左右边界与频次
- 答案二分。 答案范围宽度为 U、一次判定为 O(n) 时，总成本为 O(n log U)。
2. 半开区间不变量
在升序数组中维护 [left,right)。left 之前都小于 target，right 及之后都大于等于 target。初始 left=0、right=n，两侧已排除区域均为空。
static int lowerBound(int[] a, int target) {
int left = 0, right = a.length;
while (left < right) {
int middle = left + (right - left) / 2;
if (a[middle] < target) left = middle + 1;
else right = middle;
}
return left;
}
数组 [1,3,3,7] 查 3 返回 1，查 8 返回 4。空数组返回 0。相等时收缩右界，继续寻找更早位置。每轮区间缩短，结束时 left=right。
3. 左右边界与频次
upper bound 查找第一个严格大于 target 的位置。将代码判断改为 a[middle] <= target 即可。相等项都被排到左侧。
在 [1,3,3,7] 中，3 的两边界为 1、3。频次为 upper-lower=2，末次出现位置为 upper−1。若两边界相同，目标不存在。
直接判断大于关系可处理 Integer.MAX_VALUE。用 lowerBound(target+1) 代替上界，会在最大整数处溢出。
4. 答案范围与可行性
最小可行容量可通过单调判定求出。证明容量 c 可行后，更大容量也可行。再确认搜索上下界确实覆盖答案。
范围宽度为 U，判定一次 O(n)，总时间为 O(n log U)。单调性、范围与判定成本都属于复杂度条件。浮点二分还需定义误差或迭代次数。
5. 使用边界
lower bound 返回 n 是合法结果。读取前需检查 index<a.length，再比较是否相等。
测试应覆盖空数组、单项、重复值与两端缺失目标。中点公式适用于 0<=left<=right<=int最大值。覆盖整个有符号整数域时，差值也需提升为 long。链表缺少 O(1) 下标访问，成本见链表。
6 · 面试题卡片
本页题目与参考回答
6.1 二分遇到相等值时为何还要继续搜索？
考察重点：搜索目标与边界语义。
相关内容：半开区间不变量。
参考回答
lower bound 要求最早合格位置，所以相等时继续收缩右界。
查任意相等值时才可立即返回。统一不变量后，重复值和无解边界都能由同一循环处理。
6.2 如何用两次二分统计目标出现次数？
考察重点：左右边界、空区间与溢出。
相关内容：左右边界与频次。
参考回答
用 upper bound 减去 lower bound 即得次数。
两者分别寻找首个大于和首个大于等于目标的位置。上界直接比较大小，避免 target+1 的整数溢出。