二分查找：20 行代码里藏着的对数级智慧

如果说有一个算法能以"最小代码量"体现最高级的思维，那一定是二分查找。在一个有序数组里找一个数，它不从头找，而是每次都看正中那个元素：比目标大，就丢掉右半；比目标小，就丢掉左半。每比一次，搜索范围就减半。

数学上，长度为 n 的范围，减半 k 次后变成 1，即 2^k ≈ n，所以 k ≈ log₂ n。这意味着：100 万条数据，二分最多比约 20 次就能找到——而线性查找最坏要 100 万次。20 比 100 万，差五万倍。这就是为什么"对数级"如此迷人。

二分查找的优雅在于它是分治思想最干净的样例：把问题规模砍半、递归或迭代求解。但它有个铁前提——数据必须有序。这也解释了为什么排序（B 系列）总是排在二分前面：先花 O(n log n) 排好序，就能换来无数次 O(log n) 的快速查询，典型的"预处理换加速"。

进阶玩法叫二分答案：当答案本身满足"越大越可行/越小越不可行"的单调性时，可以不在数组上二分，而在"答案的取值范围"上二分。这类题（如"在 n 台机器上最短完成时间"）是算法竞赛常客，也是必学必会 D3 二分节点的延伸。

二分查找是必学必会算法轨道里已覆盖的节点（对应 ku_id=67），但它值得单独成文，因为它是"用对前提、指数级提速"这一算法哲学的最佳入口。

关联推荐

• GPT-5.6 递归自我改进 — 二分本质是递归分治，看它如何延伸到 AI
• （本批「算法与问题求解入门」KU 发布后回填互链）