今天是自学算法的第三天按计划该轮到二分法了。第一天还在熟悉数组和链表的基本操作第二天被双指针折磨了一阵今天打开题单看到“二分法”三个字我第一反应是这不就是猜数字吗mid (left right) / 2换两个指针完事。真等我坐下来把几道经典题刷完才发现以前对二分法的理解太片面了——它的核心不是“在有序数组里找目标”而是“把搜索范围一步步减半”。这一个认知转变直接让我把二分法从“背模板”升级成了“设计算法”的工具。这篇笔记就把我第三天的完整学习过程记录下来从最基本的整数二分到边界处理再到二分答案这种进阶用法最后附上我实际写代码时踩过的坑。不管你是刚接触算法的初学者还是准备面试想系统梳理二分法的人这篇内容应该都能帮上忙。我尽量用“我踩过坑之后才搞懂”的方式来讲让每个细节都能直接用。1. 二分法的本质能搜索的不只是数组1.1 先破一个误区数组有序不是前提区间可收缩才是很多资料开头就写“二分查找的前提是有序数组”这话没错但不完整。我第三天刷题最大的收获就是二分法真正依赖的是一个单调性关系有序只是单调性最朴素的表现形式。举个例子猜数字游戏的规则是“你猜大了还是猜小了”这就是一个典型的单调反馈数字越大反馈结果就往一个方向变。只要你能对某个目标量做出“是或否”的单调判断就能用二分法去收缩范围不一定要数组有序。再具体的场景你要在一堆日志里找某条记录的时间点日志按时间排序可以二分你要在一条单调递增的数据流里找一个阈值数据不是数组也能二分。所以理解二分法先把“有序数组查找”这个刻板印象放一抛核心是区间排除逻辑。1.2 二分法的核心不变量答案一定在当前区间里写二分最容易翻车的不是没写对 mid而是没搞清楚“当前搜索区间到底是什么”。我第二天还在用双指针习惯性地把区间定义为[left, right)所以刚开始写二分时也保留了左闭右开的习惯。后来发现不管你用哪种区间定义只要保证一个不变量就行目标答案始终落在当前区间内。我这么说可能有点抽象打个比方你在一个书架里找一本特定颜色封面的书每次从中间抽一本如果中间这本的位置比目标靠后就淘汰右半边保留左半边。因为目标这本书一定还在左半边里所以下一步就在左半边继续重复。这就是“区间不变量”——每一步收缩之后答案仍然在你保留的那个区间里。只要这个不变量成立循环就敢继续跑。一旦区间里已经没有答案或者你把答案排除在外了二分就失去了意义。这个认知是所有边界处理、循环条件、mid 偏向问题的大前提。1.3 适用三件套单调性、可比较、能随机访问我还总结了一个“二分法能不能用”的快速判断标准适合拿到题先问自己三个问题目标量是否具有单调性目标值变大时判断结果是否只会往一个方向走。判断条件是否可比较也就是每次判断后能否明确“是大了还是小了”。搜索空间能否快速定位到中点如果数据没法随机访问比如链式结构二分就不是首选。这三条都满足那恭喜你大概率能用二分。缺了任何一个要么换思路要么先把数据转成可随机访问的结构。我第三天有一道题是把链表转成数组之后才大胆用二分转之前硬写二分效率和代码复杂度都差很多。2. 手写整数二分先确定区间再管边界2.1 三种区间写法的对照别再纠结哪种是对的整数二分最大的坑就是边界。网上模板有左闭右闭[left, right]有左闭右开[left, right)甚至有左开右开每一种写法本身没错但混用就会出现各种灵异现象。我建议初学者只盯一种写法练熟我选的是左闭右闭。三种写法对照如下写法区间定义循环条件left 更新right 更新典型风险左闭右闭[left, right]while (left right)left mid 1right mid - 1忘写 -1 导致死循环左闭右开[left, right)while (left right)left mid 1right mid忘记 mid 取整方向可能漏元素左开右开(left, right)while (left 1 right)left midright mid初值设定容易晕我前两次刷题分别用了左闭右闭和左闭右开一会儿 mid - 1 一会儿 mid代码改来改去最终把自己绕晕。后来干脆固定成左闭右闭循环条件用 left right更新时如果是 mid 本身不满足条件就大胆缩掉 mid。这套写法的关键在于每次更新区间时都把 mid 排除在外因为 mid 这一轮已经检查过了。2.2 mid 的计算小心 next_plus_one 之类的问题mid left (right - left) / 2 是标准的写法用这个而不是 (left right) / 2是因为 left right 可能溢出。这个细节在算法题里经常考我在本地跑测试时因为数字小没出事但面试时如果写成 left right考官很可能就会追问一句“如果 left 和 right 都接近 int 最大值呢”。那 mid 到底取左中位还是右中位如果是左闭右闭mid left (right - left) / 2 得到的是左中位。当区间长度为奇数时mid 正好在中间长度为偶数时mid 偏左。左闭右闭 左中位是配套的不会死循环原因是每次更新时 left 至少加一区间必然收缩。如果你这时换用左闭右开还保持左中位某些场景下会出问题比如查找“第一个大于 target 的元素”时可能漏掉右边界。所以记住一句话区间写法、mid 取整方向、left/right 的更新方式是一个组合套餐不要混搭。2.3 一个 5 分钟的模板训练法要练到闭着眼都能写对我建议照下面这个流程重复三遍不参考任何资料自己手写一遍“在有序数组中查找目标值存在返回下标不存在返回 -1”。检查三个点循环条件是否带等号left 更新是否为 mid 1right 更新是否为 mid - 1。自己构造一个边界测试用例数组长度为 1目标存在于数组、目标小于数组最小值、目标大于数组最大值。我第一天写这个模板时在“目标大于数组最大值”这个用例上栽了输出居然不是 -1直接数组越界。原因是循环条件写成了 while (left right)导致 right 一直守着某个值left 越过了也没终止。把循环条件改成 left right并把更新写成 right mid - 1那个用例立刻就正常了。3. 从查找演化为判定二分答案才是二分法的进阶形态3.1 为什么“二分答案”比“二分查找”更常用三分算法题里真正难的往往不是“在数组里找某个数”而是“求一个满足条件的最小值/最大值”。这类问题表面上看不到数组没有让你查 target但答案本身是单调的此时可以把最优解问题转成判定问题再用二分去逼近答案。我第三天做了一道经典的“木头切割问题”给定几根木头的长度要切出 k 段长度相同的木头问每段最长能切多长。直接求最优解很麻烦但换个角度如果给定一个长度 x判断“能否切出 k 段”这个判定函数很好写。更妙的是长度 x 越大能切出的段数越少所以 x 和“能否满足 k 段”之间是单调关系——x 小的时候一定满足x 大的时候不一定满足二分的舞台就搭好了。3.2 判定函数的写法决定二分成败二分答案题目的核心就是写一个 check(mid) 函数返回布尔值mid 这个值能不能满足题目要求。check 好不好写决定你能不能走二分这条路。比如木头切割问题的 check 函数核心就一步遍历所有木头统计每根木头能切出多少段累加起来和 k 比较。这里要注意除法向下取整的问题如果一段木头长度为 7目标段长 x 3那么最多切 2 段不是 3 段。写成代码就是 cnt len / x注意整数除法的特性正好满足向下取整。check 函数写对了二分框架随便套左边界取 1右边界取所有木头长度的最大值或者再放宽到 maxLen循环逼近即可。二分结束后得到的 right 就是最大可能长度。3.3 最优化问题转判定问题的判断方法怎么知道一道题能不能用二分答案我的经验是看两个信号题目里出现了“最大值最小”“最小值最大”“最多/最少能满足”这类字眼。对任意给定的中间值 x你能很快算出 x 是否可行。满足这两个信号就先别急着想贪心或动态规划先想想 check(x) 怎么设计。很多时候 check 简单、二分边界清晰比硬啃复杂算法省力得多。我第二天做贪心已经很用力了第三天遇到二分答案才发现有些最优解问题本质是在一堆“可行解”里找边界而找边界二分是专用工具。4. 进阶考点查找边界值和变种问题4.1 查找第一个等于 target 的位置面试高频题从“找一个数”升级成“找这个数第一次出现的位置”。还是能用左闭右闭写但有一个关键调整当 mid 位置的元素等于 target 时不直接返回 mid而是把 right 收缩到 mid - 1继续往左找直到循环结束。此时 left 指向的才是第一次出现的位置。这个技巧的本质还是那个区间不变量当前区间里如果有目标值那么它一定不在 mid 右边已经被排除的部分里我们要把区间左边界逼向答案。我来解释下为什么 right mid - 1 而不是 right mid因为 mid 这个位置的值等于 target但它可能不是第一个所以先保留搜索左半边的可能性。如果 mid 左边已经没有目标值了循环结束后 left 就会停在 mid 处或者越过它正确结果依然能拿到。4.2 查找最后一个等于 target 的位置和查第一个形成镜像操作当 mid 等于 target 时不再收缩 right而是把 left 更新为 mid 1继续往右找当 mid 大于 target 时收缩 right当 mid 小于 target 时收缩 left。循环结束后right 指向最后一个等于 target 的位置。这里有个坑如果目标不存在最后 left 和 right 会指向一个“插入位置”你需要额外判断一下数组下标是否越界以及该位置的值是否真的等于 target。我实际调试时遇到的情况是目标值比数组中所有元素都大循环结束后 right 停在最后一个元素的下标但这个下标对应的值不等于 target如果不加判断直接返回 right就会被误判成“找到了”。4.3 旋转数组搜索和峰值查找变种题的套路笔试里二分法很少直接考“找一个数”基本都是包一层变种。第三天我做了两个典型变种旋转数组搜索——一个本来递增的数组在某一点旋转比如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。思路是每次二分先判断 mid 落在左半段还是右半段再根据 target 所在区间决定往哪边走。这个判断依赖的关键是 nums[left] nums[mid]如果成立则左半段是有序的剩下就可以用“target 是否在这个有序区间内”来决定收缩方向。峰值查找——在一个相邻元素不相等的数组里找任意一个峰值nums[i] nums[i1] 就向左收缩否则向右收缩。这题的单调逻辑不是全局有序而是一种趋势判断如果 mid 比右侧小说明峰值一定在右侧因为从左到右是在上升反之峰值在左侧。这类题的判断条件写的是“递增方向”而不是 target 比较能拓宽你对二分适用面的理解。4.4 浮点数二分精度控制和循环终止条件如果是整数二分循环条件通常是 left right换成浮点数就不能用等号比较了而是用精度控制。比如求平方根要求误差小于 1e-6循环条件就是 while (right - left eps)。浮点数二分最烦的是 eps 调太小导致死循环调太大答案不准。我的经验是eps 设置成题目要求的 1/100 到 1/1000 都够用不需要无脑设 1e-12除非特别情况。另外浮点数二分更新区间时不能像整数那样 mid 1因为浮点无法精确加减 1直接用 left mid 或 right mid 即可反正区间按精度缩小。这里也有一个新手容易困惑的地方二分次数和精度没有直接固定的转化公式。如果你担心死循环也可以用“循环固定执行 N 次”的方式比如精度 1e-6 的题循环 80 次基本稳了省得有全等判断的烦恼。这种方法在工程上也常用因为次数上限是固定的不会因为小数点位数太深而失控。5. 工程实战二分法不是只在算法题里发光5.1 C 里的 lower_bound 和 upper_bound工程上很少自己手写二分因为标准库已经帮我们封装好了。C 里 lower_bound 返回第一个大于等于 target 的迭代器upper_bound 返回第一个大于 target 的迭代器。两者相减就能得到等于 target 的元素个数这个“区间长度”技巧在写统计类代码时特别实用。我在第三天练完手写二分后又回头看了一眼标准库实现发现它其实用了左闭右开区间这更印证了前面说的“区间定义必须统一”这件事。你写代码用别人的库不要求你背内部实现但要求你懂得参数的区间语义否则很容易把 end 位置当成最后一个元素去用结果多算或漏算。5.2 Python 里的 bisect 模块Python 学习者更省事直接 import bisect里面有 bisect_left 和 bisect_right。bisect_left 找第一个不小于 target 的位置bisect_right 找第一个大于 target 的位置。写 LeetCode 时想快速实现“第一个等于 target 的元素”一行搞定。但要注意Python 内置的 bisect 默认操作对象是 list如果你的数据是其他类型需要自己实现getitem才能用 bisect这一点我在用自定义数据结构时踩过坑。后来我干脆眼写一个二分函数把比较逻辑单独抽出来反而比硬套 bisect 更灵活。5.3 业务里的二分应用从 IP 归属地到版本发布算法题里的二分法练熟以后再看实际业务就顺手多了。举个最常见的例子IP 地址归属地查询。现网里通常维护一个有序的 IP 段表比如每个段的起始 IP 和结束 IP 都排好序查询时二分定位你当前 IP 落在哪个段里。这个需求本质上就是“在有序区间里找包含点”二分比遍历要快好几个量级。再比如游戏排行榜分位数估算、日志时间范围快速检索、配置中心的版本号查找全是二分的实际应用场景。我自己的体会是算法训练不只是为了面试它会在某个看似无关的线上问题排查中突然蹦出来帮你省半小时。6. 打卡第三天的踩坑实录与总结建议6.1 死循环是怎么产生的怎么快速定位死循环是二分新手最常遇到的坑。死循环的本质是区间更新时没有收缩比如左闭右闭写法里把 right mid - 1 写成 right mid而 mid 又等于 left那么区间永远不会缩小。我排查死循环的方法很简单在 while 循环里打印 left、right、mid 三个变量跑几轮就能看到哪个变量没变化。比如打印结果显示 left 3, right 4, mid 3然后 left 变成 4, right 还是 4你会发现区间大小完全没变此时就会意识到应该是 mid - 1 写成了 mid。6.2 边界写错的表现不是报错而是答案偷偷偏移二分写错边界大概率不会立刻报异常而是给你一个差一的结果。比如查找第一个等于目标值时如果 right 收缩方式写错最后返回的可能是第二个目标值的位置甚至是不相邻的另一个相等元素的位置。这种 bug 特别隐蔽因为你看输出往往是“某个正确值”不是混乱值。我的经验是针对边界场景多写几个断言比如数组里只有一个目标元素、目标元素在开头、目标元素在结尾、目标元素不存在、数组全相同。写完这些断言再跑相当于给二分逻辑做边界测试比想破脑袋空检查代码高效得多。6.3 三天打卡的小建议一天吃透一个变种比刷十道题更值三天学下来我的感受是二分法很容易“眼高手低”看题解觉得都会一动手全是边界错。这里给同样打卡自学的人一个建议每天只针对一个二分变种把它吃透然后手写三遍。我是按这个顺序安排的第一天标准二分查找数组找 target第二天查找第一个和最后一个边界收缩第三天二分答案 旋转数组每个变种只选一到两道题但要求自己不看模板、独立手写并且跑完所有边界用例。三天下来我对二分的“手感”明显稳了不再依赖记忆模板。回头看这三天二分法的核心其实就两条一是“区间不变量”这场思维定式二是“区间写法和更新方式配套”这套工程直觉。把所有花里胡哨的变种拆开最终都落在这两条上。下一阶段我准备进入排序相关的内容到时候再看看二分法怎么和排序算法配合使用应该还会有新的收获。