二分查找：从模板到边界控制
讲清闭区间、半开区间、左边界、右边界和答案二分，重点解决死循环、漏答案和返回值混乱。
知识目录数据结构与算法：从基础到工程实践13 / 77
我对“二分查找：从模板到边界控制”的理解经历过一个从会背到会用的过程。其中最明显的一点是：二分查找是我改了最多次边界的代码之一，等号放在哪里、最后返回谁，经常靠样例碰运气。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。
二分查找看起来很简单：有序数组里，每次看中间，比目标小就往右找，比目标大就往左找。但它也是最容易写出边界 bug 的算法之一。
二分真正难的地方不是 mid，而是你有没有想清楚：当前搜索区间代表什么，哪些位置已经被排除了，最后返回哪个边界。
它从哪里来
二分查找的思想来自有序信息中的逐步排除，但早期程序实现长期容易出现边界错误。它看似只有几行，却同时涉及区间定义、中点计算、循环不变量和重复元素边界，因此成为“简单思想如何写成严格程序”的经典例子。
二分的核心思想
图：二分每一步都在缩小可能答案区间
二分适合的问题有两个共同点：
- 答案空间有顺序。
- 可以判断某个位置或答案是否满足条件，并据此排除一边。
最典型的是有序数组查找：
int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
这里使用的是闭区间 [left, right]。循环条件是 left <= right，说明区间为空的时刻是 left > right。
为什么不要写 (left + right) / 2
更稳的写法是：
int mid = left + (right - left) / 2;
原因是 left + right 在极大数组下可能整数溢出。虽然普通业务里不一定遇到，但这是一个很好的习惯：算法代码要对边界敏感。
查找左边界
很多题不是问“有没有”，而是问“第一个等于 target 的位置”。
int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
这里使用左闭右开区间 [left, right)。它返回的是第一个 >= target 的位置。如果返回位置还在数组内，并且 nums[pos] == target，它就是左边界。
int firstEqual(int[] nums, int target) {
int pos = lowerBound(nums, target);
return pos < nums.length && nums[pos] == target ? pos : -1;
}
这个模板很实用，因为它也能解决“插入位置”问题。
查找右边界
右边界可以转换成“第一个大于 target 的位置再减一”。
int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
最后一个等于 target 的位置是：
int lastEqual(int[] nums, int target) {
int pos = upperBound(nums, target) - 1;
return pos >= 0 && nums[pos] == target ? pos : -1;
}
我的建议是：边界题尽量用 lowerBound/upperBound 思维，不要在普通查找模板里硬改，否则很容易出现死循环或漏答案。
答案二分
二分不只能查数组，也能查“答案”。
比如给定若干包裹重量和天数，求船的最小运载能力。运力越大，越容易在规定天数内运完；运力越小，越难。这就是单调性。
int minCapacity(int[] weights, int days) {
int left = 0, right = 0;
for (int w : weights) {
left = Math.max(left, w);
right += w;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
boolean canShip(int[] weights, int days, int cap) {
int used = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used <= days;
}
这类题最重要的是找到判断函数 can(...)，并确认它是单调的。
常见错误
- 区间定义混乱：一会儿闭区间，一会儿半开区间。
left = mid或right = mid导致不收敛。- 忘记空数组。
- 返回
left前没有检查是否真的命中。 - 答案二分时上下界设错。
- 判断函数方向写反。
工程场景
二分在工程里也很常见：
- 日志中按时间戳查找第一条大于某时间的记录。
- 配置版本中查找生效版本。
- 数据库分页或索引定位的思想。
- 压测中查找系统最大可承载 QPS。
- 分布式系统里查找故障出现的第一个版本。
二分的价值不是只会写数组查找，而是建立“单调性 + 排除一半”的思维。
面试题
while(left <= right)和while(left < right)有什么区别？- 为什么
lowerBound返回的是第一个>= target的位置？ - 二分为什么可能死循环？如何避免？
- 什么样的问题可以做答案二分？
- 如果数组有重复元素，如何找第一个和最后一个目标值？
小结
二分的灵魂是区间不变量。只要你能说清楚区间含义、排除逻辑和最终返回值，二分就不会再靠运气。后面很多高级题，本质上只是把数组位置换成了答案空间。
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《二分查找：从模板到边界控制》及其公开关联内容中检索，并把引用定位回原文章节。