C / C++ / 系统课时

二分查找为什么必须有序

二分查找为什么必须有序

二分查找能把搜索区间一再减半,关键并不是“从中间开始找”,而是数组已经有序,使一次大小比较就能排除整整一半元素。本节将实现迭代版二分查找,并验证这个有序条件如何支撑算法成立。

学习目标

  • 理解有序数组为何能根据一次比较排除半个搜索区间
  • 使用 C 实现迭代版二分查找并验证结果
  • 区分二分查找的必要条件与普通顺序查找的适用场景

一次比较为什么能排除一半

假设数组按升序排列,当前搜索区间为 left 到 right,中点为 mid。如果目标值小于 array[mid],那么 mid 右侧元素都不可能等于目标值,因为它们只会更大;反之,目标值大于中点时,左侧也可以整体排除。

有序数组中二分查找逐步缩小搜索区间

这里真正有用的是顺序关系。如果数据无序,看到中间元素为 20、目标值为 15,并不能推出 15 一定在左边;它完全可能出现在右半部分,因此不能安全丢弃任何一半。

用迭代方式实现

下面使用闭区间 [left, right]。只要 left <= right,区间中仍然至少有一个待检查元素。计算中点时使用 left + (right - left) / 2,可以避免直接执行 (left + right) / 2 时潜在的整数加法溢出。

c
#include <stdio.h>

int binary_search(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;
        }

        // 中点已经检查过,因此新的区间必须排除 mid。
        if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int numbers[] = {3, 8, 12, 17, 23, 31, 46, 59};
    int length = (int)(sizeof(numbers) / sizeof(numbers[0]));
    int target = 23;

    int index = binary_search(numbers, length, target);
    printf("target=%d, index=%d\n", target, index);

    return 0;
}

预期输出

text
target=23, index=4

数组下标从 0 开始,因此 23 位于索引 4。如果目标不存在,循环最终会使 left > right,函数返回 -1。

有序条件怎样改变复杂度

顺序查找最坏情况下需要逐个检查 nn 个元素,时间复杂度为 O(n)O(n)。二分查找每比较一次都把候选区间缩小约一半,最多经历约 log⁡2n\log_2 n 次比较,因此时间复杂度为 O(log⁡n)O(\log n)。

这种优势的前提仍然是“数据已经按同一种比较规则有序”。如果每次查询前都临时排序,还要额外承担排序成本;对于只查一次的小数组,直接顺序查找可能反而更简单。

无序数据为什么不能直接套用

例如数组 {3, 31, 8, 46, 12} 的中间元素是 8。查找 31 时,因为 31 > 8 就丢弃左半部分,会把真正的目标一起排除。算法并不是偶尔变慢,而是失去了正确性保证。

实际使用二分查找前,应先确认数据的排序方向和比较规则。只要这一前提成立,每次比较才能可靠地消除一半候选元素,这正是二分查找高效且正确的根本原因。

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

目录与阅读设置

阅读设置

17

记录一个想法

二分查找为什么必须有序

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

登录哪都通