问一个扎心的问题不看答案你能一次写对二分查找吗我猜很多写了十年代码的人都会在这个问题上卡壳——不是不会是边界总出 bug。要么while (left right)和while (left right)傻傻分不清要么right mid和right mid - 1纠结半天要么最后返回left还是right全靠蒙。二分查找一共不到十行代码却是程序员界的bug 重灾区。为什么因为大多数人学二分是背模板。模板这东西场景一变就失效——找等于是一种写法找第一个大于等于又是一种写法背来背去全乱了。这篇文章不给你背模板给你一样更值钱的东西循环不变量Loop Invariant。搞懂它二分的所有边界你都能自己推出来。二分查找的本质每次砍掉一半不可能先回到那个最朴素的直觉。你要在一排从小到大排好序的数字里找一个目标。二分的思路谁都懂看一眼中间那个数——中间数等于目标找到了中间数比目标小那目标只可能在右半边因为左边都比它更小中间数比目标大那目标只可能在左半边。然后缩小范围重复。每一步都严格地砍掉一半绝对不可能的区间。这也是二分为什么快到离谱的原因它每看一眼就把搜索空间对半切。一亿个数最多看 27 次就够了2 27 ≈ 1.3 × 10 8 2^{27} \approx 1.3 \times 10^8227≈1.3×108。这个直觉人人都会。那 bug 从哪来从边界来——砍的时候左指针和右指针到底该怎么动动完还剩几个数最后停在哪。这些细节才是二分的灵魂也是最容易错的地方。先纠一个经典 bug(left right) / 2会溢出在讲边界之前先干掉一个技术性的坑。很多人写中点mid (left right) / 2。看着没问题但left right可能溢出——当两个数都很大时加起来超过了整型能表示的范围结果就成了负数数组下标直接爆炸。正确写法是midleft(right-left)//2right - left不会溢出left (right - left)/2就等于中点。这是个经典细节面试官很爱考。核心心法先定区间再定边界二分的所有边界争议根源只有一个——你脑子里的当前区间到底是什么含义没定清楚。一个数组怎么表示正在搜索的区间有两种主流的约定闭区间[left, right]左右端点都可能是答案左闭右开区间[left, right)左端点可能是答案右端点不算。约定不同代码就不同。边界不是背出来的是你的区间定义这个不变量推出来的。这就是为什么背模板会乱——你背了 A 约定的循环条件配了 B 约定的指针更新当然全是 bug。约定一闭区间[left, right]假设我们约定答案如果存在一定落在闭区间[left, right]里左右都含。那么循环什么时候继续只要区间里还有数可查——也就是left right。当left right时区间空了结束。指针怎么动算出mid后如果arr[mid] target找到直接返回如果arr[mid] target那mid及其左边都不可能是答案区间收缩为[mid 1, right]所以left mid 1如果arr[mid] target那mid及其右边都不可能是答案区间收缩为[left, mid - 1]所以right mid - 1。注意这里left mid 1和right mid - 1都严格地把 mid 排除掉了——因为闭区间里我们看过 mid 了它不是答案。写成代码defbinary_search(arr,target):left,right0,len(arr)-1whileleftright:# 区间 [left, right] 非空midleft(right-left)//2ifarr[mid]target:returnmidelifarr[mid]target:leftmid1# 收缩为 [mid1, right]else:rightmid-1# 收缩为 [left, mid-1]return-1# 没找到约定二左闭右开[left, right)现在换个约定答案落在[left, right)里right本身不算。循环条件呢区间非空 left right当left right时[left, left)是空的结束。指针怎么动如果arr[mid] target返回如果arr[mid] target区间收缩为[mid 1, right)所以left mid 1如果arr[mid] target区间收缩为[left, mid)所以right mid——注意这里不是mid - 1因为右端点是开的mid本来就不在区间里直接right mid就好。defbinary_search_half_open(arr,target):left,right0,len(arr)# 注意 right len(arr)因为右端点不算whileleftright:# 区间 [left, right) 非空midleft(right-left)//2ifarr[mid]target:returnmidelifarr[mid]target:leftmid1else:rightmid# 右开所以是 right midreturn-1看明白了吗两种写法循环条件、指针更新都不一样但它们各自内部是自洽的。你只要死死守住我的区间是什么约定边界自然就对了。乱的根源永远是约定没想清楚。进阶lower_bound 和 upper_bound只写查找等于还不够。二分查找真正高频的用法是两个更实用的变体lower_bound找第一个大于等于 target 的位置upper_bound找第一个大于 target 的位置。这俩在 C 里是std::lower_bound/std::upper_bound在工程里是无数算法如求插入位置、求区间个数的地基。它们的写法同样用不变量一次推出来。推导lower_bound我们要找第一个 target的下标。维持这样一个不变量left的左边不含 left都是 target的right的右边含 right都是 target的答案一定在[left, right)里。如果arr[mid] target说明mid及左边都 target答案在右边left mid 1如果arr[mid] target说明mid可能是答案也可能在左边答案在[left, mid]里right mid右开所以不含 mid 的写法就是 right mid。循环结束left right时left正好指向第一个 target的位置。从头到尾你脑子里只放一件事left之前都小于 target。这个不变量一旦守住最后left就是答案根本不用纠结返回谁。deflower_bound(arr,target):left,right0,len(arr)whileleftright:midleft(right-left)//2ifarr[mid]target:leftmid1else:rightmidreturnleft# 第一个 target 的下标upper_bound只改一个符号——把 target往右赶换成 target往右赶defupper_bound(arr,target):left,right0,len(arr)whileleftright:midleft(right-left)//2ifarr[mid]target:leftmid1else:rightmidreturnleft# 第一个 target 的下标手算一遍把不变量刻进脑子拿数组[1, 3, 3, 5, 7]target 3手算lower_bound初始left0, right5区间[0,5)mid 2arr[2]33 3所以right 2区间[0,2)mid 1arr[1]33 3所以right 1区间[0,1)mid 0arr[0]11 3所以left 1区间[1,1)空了结束left 1。查表arr[1]3确实是第一个 3。✅再算upper_bound第一个 3mid2arr[2]33 3left 3mid4arr[4]77 3right 4mid3arr[3]55 3right 3结束left 3。arr[3]5确实是第一个大于 3 的位置。✅两次手算你全程只要盯着一个念头“left之前都满足某个条件”。这就是不变量。它没让你记任何模板却让你每一步都确定无疑。二分的边界其实是一道思维体操很多算法书把二分写成好几种模板让人越背越晕。但拆到最底层它只是一件事先严格定义搜索区间再守住一个循环不变量让每一步收缩区间时不变量都保持不变。循环结束时不变量自然把答案逼到left上。这其实是整个算法设计的通用心法二分的边界只是它最简单的练兵场。快排的分区、动态规划的状态转移、并查集的合并……背后全都是同一个词不变量。你把二分的不变量练透了看别的算法会突然通透很多。结语别背模板守不变量回到开头那个问题二分为什么总写错因为你在背哪种情况用哪个等号、加不减一而不是在理解我的区间是什么、我的不变量是什么。背的东西会忘、会串推出来的东西才会长在脑子里。下次写二分先花十秒钟在心里默念一句话——“我现在的区间是[left, right]还是[left, right)我守住的不变量是什么”念完这两句边界自己就浮出来了根本不用背。二分查找、排序、图……这些算法题里的基本功最值得系统啃一遍。推荐 B站【408实验室】的《数据结构》打底再用 CoLearnyantucs.com的 AI 答疑把卡壳的地方逐个问明白——别让背模板耽误了你真正懂算法。