一、二分查找基础别再从头一个个数了1.1 二分查找的概念与原理像个心机的“猜数字”玩家在计算机科学的江湖里二分查找就像是一个“心机Boy”。它绝不干那种从头开始傻乎乎挨个数的体力活而是专门在有序数组这个规矩的圈子里用最少的步骤精准KO目标。它还有个名字叫“折半查找”听着挺高大上其实就是“对半砍”。它的核心哲学是既然队伍是排好序的那我就直接跳到队伍中间问一句“喂目标在你们那边还是这边”举个栗子假设我们有一个有序数组 [1, 3, 5, 7, 9, 11, 13]我们要找 15。普通人的做法是1不是。3不是。5不是……累死。二分查找的做法是直接站在中间9的位置大喊一声“15在哪”因为 9 15数组这头太小了目标肯定在右边那群“高个子”里。于是它直接把左边一半人“咔嚓”划掉不管了。接着在右半场 [11, 13] 中间站再喊“15在哪”13 还是小于 15继续把 13 左边的虽然没剩几个了划掉。最后发现没人了得出结论15 这家伙根本不在这个数组混。这招数叫“剥洋葱”有点太温柔了我觉得叫“切西瓜”更贴切。每次一刀下去不要的那一半直接扔进垃圾桶效率极高。相比于普通人 O(n) 的线性查找数据多十倍时间多十倍二分查找是 O(logn) 的数据多十倍时间只多一点点简直是算法界的“流氓”。1.2 二分查找的实现步骤别把边界写崩了写二分查找代码就像在走钢丝一不小心就会“摔死”死循环或数组越界。首先我们要划定地盘左边界 left 0右边界 right n-1。然后进入循环只要 left right就说明还有地盘可搜。中间位置 mid 怎么算你可能会写 (left right) / 2。停别这么干如果 left 和 right 都是接近内存上限的大数它们一加直接溢出变成负数程序就崩了。我们要用点黑科技mid left (right - left) / 2。这样先减后加稳如老狗。算出 mid 后就拿 arr[mid] 和目标值比如果相等恭喜你抓到了直接 return。如果 arr[mid] target说明目标在右边左边界收缩left mid 1。如果 arr[mid] target说明目标在左边右边界收缩right mid - 1。很多新手在这里容易犯“手抖病”写成 left mid 或 right mid。千万别因为 mid 位置已经比过了肯定不是目标再包含它就是浪费时间甚至导致死循环。一定要把比过的点“剔除”出去。二、二分查找的应用场景不仅仅是找数2.1 在有序数组中查找元素精准打击还是那个数组 [1, 3, 5, 7, 9, 11, 13]找 7。开局left0, right6。第一刀mid3, 值是 5。5 7所以把 5 及其左边全扔了left 4。第二刀mid5, 值是 11。11 7把 11 及其右边全扔了right 4。第三刀mid4, 值是 7。Bingo你看7个数只用了3次就找到了。如果数组有一亿个数二分查找最多也只需要找大约27次因为 2^27 约等于一亿多。这种效率让暴力查找只能跪下唱《征服》。2.2 寻找插入位置给新来的找个座有时候我们不需要找存在的数而是想知道如果要把一个数插进去应该插在哪才能不破坏数组的有序性。比如在 [1, 3, 5, 7, 9, 11, 13] 中插入 8。按照二分逻辑mid3, 值是 5。5 8说明 8 应该在右边left 4。mid5, 值是 11。11 8说明 8 应该在左边但包含11的位置right 4。此时 left4, right4。mid4, 值是 7。7 8所以 left mid 1 5。现在 left5, right4循环结束。注意此时 left 的值就是插入点。因为当循环结束时left 指向的是第一个比目标值大的位置。所以 8 应该插在下标 5 的位置也就是 9 的前面完美三、二分答案入门当“猜数字”变成了“猜答案”3.1 二分答案的定义与思想暴力穷举的“作弊”版如果说二分查找是在“有序的数组”里找数那二分答案就是在“有序的答案范围”里找解。它就像是一个考试只会在选择题里蒙答案的老油条。题目很难不会做没关系只要知道答案肯定在 0 到 100 之间而且具有单调性比如猜大了就不行猜小了就行那就可以二分答案。经典例子切绳子。有一堆绳子长度分别是 [5, 8, 10]我要把它们切成 6 段问每段最长能有多长普通人可能会从 1cm 开始试切 1cm 能切很多段行切 2cm 也能行……一直试到切不动为止。这叫线性查找太慢。二分答案玩家会这样想每段长度肯定在 0 到最长绳子10之间。我先猜中间值 5cm。切 5cm5/51段8/51段10/52段总共 4 段。不够 6 段说明切大了得切小点。于是把右边界缩小到 5。再猜中间值 2cm。切 2cm5/22段8/24段10/25段总共 11 段。大于 6 段说明切小了可以试着切大点。于是把左边界扩大到 2。如此反复很快就能逼近那个“刚刚好能切出6段”的最大长度。核心逻辑是如果 x 可行那么所有比 x 小的都可行如果 x 不可行所有比 x 大的都不可行。利用这种单调性我们就能二分。3.2 二分答案适用的问题类型当“暴力”太丑陋时当你遇到以下类型的问题且数据量很大n 到 10^5 或更大时二分答案往往是救星“求最大值最小”或“求最小值最大”。比如“让最短的那段尽量长”。“判断是否存在一个方案满足条件”且方案具有单调性。传统的暴力枚举O(n) 或 O(n^2)会超时但验证一个猜测的复杂度很低比如 O(n)。四、二分答案的经典案例从理论到实战4.1 数的范围问题寻找边界在数组 [1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9] 中找 5 的起始和结束位置。找起始位置左边界我们二分查找当 arr[mid] 5 时不要急着返回因为可能左边还有。我们要把搜索范围强行拉到左边right mid - 1。当循环结束时left 通常就是第一个 5 的位置。找结束位置右边界同样二分当 arr[mid] 5 时去右边找left mid 1。循环结束时right 通常就是最后一个 5 的位置。这叫“二分下界的技巧”核心在于等于的时候不要停要继续往左或右逼近直到把边界“挤”出来。4.2 木材加工问题实数二分的尴尬有一堆木材 [5, 8, 10, 12, 15, 18, 20]要切出 10 段等长的木头求最长长度。这和切绳子一样。但注意长度可能是小数比如 8.333米。这时候整数二分的 left right 就不好用了因为实数是连续的。我们需要设定一个精度比如 1e-60.000001。循环条件变成while (right - left 1e-6)中间值 x (left right) / 2。验证 x 是否可行调整边界。最后输出 left 或 right 或它们的平均值即可。实数二分的关键在于控制好精度别让计算机去死磕两个无限接近的数。五、二分查找与二分答案的对比表兄弟的异同5.1 相同点与联系换汤不换药这俩货本质上是一回事核心都是“分治”和“单调性”。代码长得几乎一模一样都有 left、right、mid都有 while 循环都要根据条件收缩边界。时间复杂度都是 O(logn)都是效率极高的算法。二分查找可以说是二分答案的一个特例二分查找是在数组下标这个“有序序列”里二分二分答案是在“解空间”里二分。5.2 不同点与区别找的东西不一样二分查找找的是“存在的东西”。数组里必须有这个数你才能找到它。二分答案找的是“最优的东西”。这个答案可能在原数组里根本不存在它是通过逻辑推导出来的。二分查找的逻辑通常是比较大小相等就赢了。二分答案的逻辑通常是模拟验证可行就往大了猜不可行就往小了猜。六、二分查找与二分答案的优化技巧别让细节坑了你6.1 边界条件的处理死循环的元凶写二分最怕死循环。比如在找左边界时如果写成了 left mid当 left 和 right 相邻时mid 算出来等于 left赋值后 left 还是等于 mid这就死循环了。记住口诀查找时不包含 mid1/-1收缩时保留 mid因为可能就是解。对于整数溢出坚决使用 left (right - left) / 2。对于实数二分不要用 判断要用精度控制。6.2 时间复杂度的优化常数优化虽然复杂度都是 O(logn)但能快一点是一点。计算 mid 时位运算比除法快mid left ((right - left) 1)。虽然现代编译器通常会自动优化但写出来显得你懂汇编。如果验证一个猜测的代价很高比如 O(n)可以尝试优化验证函数的逻辑或者利用数据结构如前缀和把验证复杂度降下来。七、实际应用案例这玩意儿真能赚钱7.1 在数据库查询中的应用索引的底层逻辑为什么数据库给字段加了索引后查询飞快因为索引如B树底层就是利用了二分的思想。没有索引查100万条数据可能要扫全表。有索引查100万条数据大概只需要 20 次磁盘IOlog2(1000000) ≈ 20。这就是二分查找改变世界的地方。下次老板问你为什么要加索引你就说这是“二分法的降维打击”。7.2 在算法竞赛中的应用上分神器在ACM/ICPC或者LeetCode周赛中二分答案是中等题和困难题的常客。遇到“最大化最小值”这种绕口令一样的题目别犹豫直接套二分答案模板。设定 low 和 high写个 check 函数然后二分。只要 check 函数逻辑正确这道题基本就稳了。这招被称为“二分答案大法好”是竞赛选手从暴力选手进化成优雅选手的标志。总之二分查找和二分答案虽然初看有点绕但一旦掌握了“单调性”和“边界处理”这两个核心你会发现它们是算法世界里最简单、最暴力、最高效的工具。别再暴力 for 循环了学会二分你就是整条街最靓的仔