缺陷定位：从现象到根因
题目3：二分查找法——从原理到实战
二分查找，说白了就是“猜数字”游戏的高级版。你心里想一个1到100之间的数，我每次猜中间值，你告诉我大了还是小了。最多7次，我就能猜中。这就是二分查找的核心思想。
我个人习惯把二分查找叫做“折半搜索”。它要求数据必须是有序的。每次比较中间元素，就能排除掉一半的搜索范围。这个效率，比从头到尾遍历快太多了。
我在项目中遇到过不少情况，明明数据量不大，但程序就是慢得离谱。一查，发现有人在用线性搜索遍历一个百万级的列表。换成二分查找后，响应时间从秒级降到了毫秒级。嗯，这就是算法的力量。
二分查找原理
原理其实很简单。三个指针：左边界、右边界、中间点。每次比较中间点的值，然后决定往左还是往右搜。
我给大家一个标准实现，注意看边界条件：
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}这里有个细节：mid = left + (right - left) / 2。为什么不用 (left + right) / 2？因为 left 和 right 都很大的时候，加起来可能溢出。你想想看，这个坑我踩过不止一次。
核心要点：
- 数据必须有序，否则二分查找无效
- 边界条件要小心：left <= right 还是 left < right？
- mid 计算防溢出
- 每次更新 left 或 right 时，要跳过 mid
在代码调试中的应用
二分查找不只是用来查数据的。它还是调试利器。我经常用它来定位bug。
想象一下：你有一个程序，运行到某个点就崩溃了。但代码有几千行，你总不能一行行看吧？这时候，二分查找就派上用场了。
具体怎么做？
- 找到代码的起点和终点
- 在中间位置加个断点或打印语句
- 运行程序，看崩溃发生在断点之前还是之后
- 缩小范围，重复这个过程
我曾经用这个方法，在10万行代码里定位一个内存泄漏。只用了7次二分，就找到了那个忘记释放资源的函数。效率惊人。
调试小技巧：
用二分法定位bug时，不要只加一个断点。我习惯在二分点前后各加一个断点，这样能更快确认问题范围。
实战案例：定位数组越界
数组越界是C/C++程序员的噩梦。它不会立即报错，而是悄悄破坏内存。等程序崩溃时，你根本不知道是哪一行代码干的。
有一次，我接手一个遗留系统。程序运行半小时后必崩。日志里没有任何异常信息。我怀疑是数组越界。
怎么用二分查找定位？
第一步，找到所有操作数组的地方。这个项目有200多处数组访问。我按时间顺序把它们排好。
第二步，在中间位置加个检查。比如在第100处数组访问前后，打印数组索引和边界值。
第三步，运行程序。如果崩溃发生在第100处之前，说明问题在前半段。否则在后半段。
就这样，我用了6次二分，锁定了第23处数组访问。代码是这样的：
for (int i = 0; i <= n; i++) { // 注意这里用了 <=，应该是 <
buffer[i] = data[i];
}看到问题了吗？i <= n 多了一次循环。当 i 等于 n 时，buffer[n] 已经越界了。因为数组索引从0开始，最后一个元素是 buffer[n-1]。
避坑指南：
我曾经在二分查找的边界条件上栽过跟头。写 while (left < right) 还是 while (left <= right)？我的经验是：统一用 left <= right，然后 mid 比较后 left 和 right 都跳过 mid。这样不容易出错。
知识体系图
下面这张图，是我自己总结的二分查找知识体系。从原理到调试，再到实战，一目了然。
这张图把二分查找的三个维度串起来了。原理是基础，调试是应用，实战是检验。三者缺一不可。
总结一下：
- 二分查找原理简单，但边界条件容易出错
- 调试时用二分法，能快速定位bug范围
- 数组越界这类问题，用二分法排查效率极高
- 写代码时注意循环边界，多用
<少用<=
嗯，二分查找就讲到这里。记住一句话：能用二分解决的问题，不要用线性。不管是查数据还是查bug，这个道理都适用。
可可精品资料库