# 二分查找（Binary Search）图解：窗口怎样缩小

逐步观察 lo、hi、mid，比较正确更新与窗口停滞，区分未命中和死循环。

原文 / Canonical: https://crazycloud.cc/learn/binary-search
作者: crazycloudcc
首次发布: 2026-10-07
更新: 2026-10-07

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

二分查找在有序数组中比较中点，每轮排除不可能的一半。本页闭区间版本命中时返回一个匹配下标，否则返回 -1。

## 适用条件与边界

输入按非下降顺序排列，允许重复；数组可随机访问。重复目标只保证找到一个，不保证最左或最右。空数组直接返回 -1。图形输入限制为 1–8 个 ±999 整数，这不是算法本身的限制。

## 不变量

目标若存在，就仍在闭区间 [lo, hi] 中。正确更新为 lo = mid + 1 或 hi = mid - 1；lo > hi 时返回 -1。

## 逐步例子

1. 在 [1, 3, 5, 7, 9] 中找 9：lo = 0，hi = 4，mid = 2，a[mid] = 5 < 9。
2. 排除中点及左侧：lo = 3，hi = 4，mid = 3，a[mid] = 7 < 9。
3. 再令 lo = 4，hi = 4，mid = 4，命中 9，返回下标 4。

## 复杂度

迭代查找最坏时间 O(log n)，额外空间 O(1)；空数组 O(1)。不包含预先排序的成本，也不包含页面为动画保存轨迹的开销。

## 常见误区

- 闭区间未命中后写 lo = mid 或 hi = mid，可能保留同一窗口而停滞。不要混用闭区间和半开区间模板。
- 未排序就二分，排除一半的依据不成立；排序还会改变原始下标。
- C++ 使用 lo + (hi - lo) / 2 时，仍须保证下标和差值可表示；有符号整数溢出是未定义行为，本页小整数不模拟它。

## 自测

[1, 3] 查找 3，第一次 mid = 0。若写 lo = mid，下一轮窗口是什么？

仍是 [0, 1]，中点也仍是 0。窗口没有缩小。改成 lo = mid + 1 后窗口变为 [1, 1]，下一轮命中。

## 参考资料

- [CP-Algorithms：Binary Search（不变量与复杂度）](https://cp-algorithms.com/num_methods/binary_search.html)

[推导与 C++ 代码](https://crazycloud.cc/blog/binary-search)