C / C++ / 系统课时
二分查找为什么必须有序
二分查找为什么必须有序
二分查找能把搜索区间一再减半,关键并不是“从中间开始找”,而是数组已经有序,使一次大小比较就能排除整整一半元素。本节将实现迭代版二分查找,并验证这个有序条件如何支撑算法成立。
学习目标
- 理解有序数组为何能根据一次比较排除半个搜索区间
- 使用 C 实现迭代版二分查找并验证结果
- 区分二分查找的必要条件与普通顺序查找的适用场景
一次比较为什么能排除一半
假设数组按升序排列,当前搜索区间为 left 到 right,中点为 mid。如果目标值小于 array[mid],那么 mid 右侧元素都不可能等于目标值,因为它们只会更大;反之,目标值大于中点时,左侧也可以整体排除。

这里真正有用的是顺序关系。如果数据无序,看到中间元素为 20、目标值为 15,并不能推出 15 一定在左边;它完全可能出现在右半部分,因此不能安全丢弃任何一半。
用迭代方式实现
下面使用闭区间 [left, right]。只要 left <= right,区间中仍然至少有一个待检查元素。计算中点时使用 left + (right - left) / 2,可以避免直接执行 (left + right) / 2 时潜在的整数加法溢出。
#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;
}预期输出
target=23, index=4数组下标从 0 开始,因此 23 位于索引 4。如果目标不存在,循环最终会使 left > right,函数返回 -1。
有序条件怎样改变复杂度
顺序查找最坏情况下需要逐个检查 个元素,时间复杂度为 。二分查找每比较一次都把候选区间缩小约一半,最多经历约 次比较,因此时间复杂度为 。
这种优势的前提仍然是“数据已经按同一种比较规则有序”。如果每次查询前都临时排序,还要额外承担排序成本;对于只查一次的小数组,直接顺序查找可能反而更简单。
无序数据为什么不能直接套用
例如数组 {3, 31, 8, 46, 12} 的中间元素是 8。查找 31 时,因为 31 > 8 就丢弃左半部分,会把真正的目标一起排除。算法并不是偶尔变慢,而是失去了正确性保证。
实际使用二分查找前,应先确认数据的排序方向和比较规则。只要这一前提成立,每次比较才能可靠地消除一半候选元素,这正是二分查找高效且正确的根本原因。