C / C++ / 系统课时
二分查找边界为什么容易错
二分查找边界为什么容易错
二分查找的主体只有几行,却很容易出现漏查最后一个元素、越界或死循环。问题通常不在比较本身,而在区间定义、循环条件和边界更新没有保持同一套规则。本节用闭区间与半开区间两种写法建立可检查的边界约定。
学习目标
- 理解闭区间与半开区间对应的循环条件和更新规则
- 识别
mid没有被排除所导致的死循环 - 编写并验证两种边界一致的二分查找实现
先决定区间表示
二分查找最好先明确“当前候选元素到底在哪个区间里”,再写循环。两种常见约定都正确,但不能把它们的规则混用。
| 区间约定 | 初始右边界 | 循环条件 | 向左缩小时 | 向右缩小时 |
|---|---|---|---|---|
闭区间 [left, right] |
length - 1 |
left <= right |
right = mid - 1 |
left = mid + 1 |
半开区间 [left, right) |
length |
left < right |
right = mid |
left = mid + 1 |
闭区间中的 right 指向一个真实候选元素,所以 left == right 时还必须检查一次。半开区间的 right 本身不属于候选范围,因此当 left == right 时区间已经为空。
死循环通常怎样产生
下面是一个常见错误。它采用闭区间条件 left <= right,却在目标位于右侧时执行 left = mid。
片段示例,假设 array、target、left 和 right 已在外层二分查找函数中定义:
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] < target) {
left = mid; // 错误:mid 仍被保留在下一轮区间中
} else {
right = mid - 1;
}
}当区间只剩两个元素,例如 left = 6、right = 7 时,整数除法得到 mid = 6。若仍需向右查找,执行 left = mid 后 left 还是 6,下一轮又得到相同的 mid,区间没有缩小,循环便无法结束。
两种正确写法
下面的完整程序分别实现闭区间和半开区间版本,并使用同一组测试数据验证结果。两种函数的关键不是代码长得一样,而是各自内部始终遵循自己的区间不变量。
#include <stdio.h>
int search_closed(const int array[], int length, int target) {
int left = 0;
int right = length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
}
if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int search_half_open(const int array[], int length, int target) {
int left = 0;
int right = length;
while (left < right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
}
// right 不属于区间,因此向左时可以直接令 right = mid。
if (array[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return -1;
}
int main(void) {
int numbers[] = {4, 9, 15, 21, 28, 36, 50};
int length = (int)(sizeof(numbers) / sizeof(numbers[0]));
printf("closed: %d\n", search_closed(numbers, length, 50));
printf("half-open: %d\n", search_half_open(numbers, length, 50));
printf("missing: %d\n", search_closed(numbers, length, 22));
return 0;
}预期输出
closed: 6
half-open: 6
missing: -1这个测试特意包含数组最后一个元素 50。如果误把闭区间循环写成 left < right,当搜索收缩到 left == right == 6 时会直接退出,从而漏查最后一个候选位置。
用不变量检查边界代码
调试二分查找时,不必死记某一份模板,可以连续检查三个问题:当前候选元素是否全部位于约定区间内;mid 已确定不是答案后是否被下一轮排除;每次循环后区间长度是否严格变小。
闭区间长度可以理解为 right - left + 1,半开区间长度为 right - left。只要一次更新后长度可能保持不变,就存在死循环风险;如果更新提前移除了尚未检查的位置,则可能产生漏查。
边界错误之所以常见,是因为循环条件、初始值和更新规则彼此依赖。实际编码时先选定 [left, right] 或 [left, right),再让所有语句服从同一个区间定义,比单独记住某几行二分查找模板更可靠。