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 已在外层二分查找函数中定义:

c
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,区间没有缩小,循环便无法结束。

两种正确写法

下面的完整程序分别实现闭区间和半开区间版本,并使用同一组测试数据验证结果。两种函数的关键不是代码长得一样,而是各自内部始终遵循自己的区间不变量。

c
#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;
}

预期输出

text
closed: 6
half-open: 6
missing: -1

这个测试特意包含数组最后一个元素 50。如果误把闭区间循环写成 left < right,当搜索收缩到 left == right == 6 时会直接退出,从而漏查最后一个候选位置。

用不变量检查边界代码

调试二分查找时,不必死记某一份模板,可以连续检查三个问题:当前候选元素是否全部位于约定区间内;mid 已确定不是答案后是否被下一轮排除;每次循环后区间长度是否严格变小。

闭区间长度可以理解为 right - left + 1,半开区间长度为 right - left。只要一次更新后长度可能保持不变,就存在死循环风险;如果更新提前移除了尚未检查的位置,则可能产生漏查。

边界错误之所以常见,是因为循环条件、初始值和更新规则彼此依赖。实际编码时先选定 [left, right] 或 [left, right),再让所有语句服从同一个区间定义,比单独记住某几行二分查找模板更可靠。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二分查找边界为什么容易错

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通