二分查找堪称算法界的“翻车之王”——《编程珠玑》里Jon Bentley曾统计专业程序员中能一次写对二分查找的不到 10%。边界条件、死循环、溢出、漏解……坑比代码多。更恶心的是普通的二分查找只能找到“某个”target而面试最爱考的是有重复元素时找第一个和最后一个target。LeetCode34这道题就是专门用来治你“二分边界强迫症”的。今天我们用一套循环不变量方法一次写对lower_bound和upper_bound从此告别死循环。顺带解锁高阶技能——二分答案。 题目速览30 秒读懂给定一个非递减数组nums和目标值target找出target在数组中的第一个和最后一个位置。不存在则返回[-1, -1]。示例nums [5,7,7,8,8,10],target8→ 输出[3,4]示例target6→ 输出[-1,-1]约束必须O(logn)时间复杂度数组长度1e5。重复元素是本题的全部难点。 核心思路把“找等于”改成“找分界点”普通二分为什么不够[5,7,7,8,8,10]找8普通二分可能命中最左边的8下标3也可能命中右边的下标4——完全随机。而且命中就返回根本没机会确认边界。重新定义问题找“第一个满足条件的位置”引入两个强大的语义C STL 经典命名lower_bound(x)第一个≥ x的位置upper_bound(x)第一个 x的位置然后答案就变成了一句优雅的翻译第一个 target lower_bound(target)最后一个 target upper_bound(target) - 1关键跃迁二分的本质从来不是“找值”而是在一个单调序列上找false/true的分界点。对于lower_bound(target)谓词是nums[mid] target——前半段全是false后半段全是true我们要找的就是第一个true 的位置。循环不变量写对二分的心法口诀以左闭右闭区间[lo, hi]为例全程维护一个不变式[lo-1]及其左边全部不满足条件[hi1]及其右边全部满足条件——答案永远藏在[lo, hi]里。如果nums[mid] target→ mid及左边都不满足 →lo mid 1如果nums[mid] target→ mid满足可能是答案→hi mid保留 mid循环结束于lo hi此时lo就是第一个满足条件的位置。死循环是怎么来的hi mid时mid必须下取整(lohi)//2否则lo, hi相邻时midlolomid会导致原地踏步。lo mid时mid必须上取整(lohi1)//2否则同样会死循环。一句话口诀收缩方向和取整方向必须错开保证每轮区间严格缩小。️ 图解算法手把手走一遍nums [5,7,7,8,8,10],target 8求lower_bound(8)第一个 ≥ 8轮次lohimidnums[mid]条件8动作10527❌ 否lo 323548✅ 是hi 433438✅ 是hi 3结束33——lo hi答案 3 ✅求upper_bound(8)第一个 8条件换成nums[mid] 8轮次lohimidnums[mid]条件8动作10527❌lo 323548❌lo 5结束55——lo hi答案 5 ✅最后一个 8 的位置 5 - 1 4。最终[3,4]✅ 代码实现Python JavaPython 版最优雅写法classSolution:defsearchRange(self,nums:List[int],target:int)-List[int]:loself.lower_bound(nums,target)# 不存在的情况越界或值不相等iflolen(nums)ornums[lo]!target:return[-1,-1]hiself.lower_bound(nums,target1)-1# 右边界巧妙return[lo,hi]deflower_bound(self,nums,target):返回第一个 target 的下标C lower_bound 语义lo,hi0,len(nums)-1whilelohi:# 区间非空mid(lohi)//2# 下取整配合 himidifnums[mid]target:lomid1# mid 不满足排除else:himid# mid 满足保留候选iflen(nums)0ornums[lo]target:returnlen(nums)returnlo# lo hi收敛Java 版完整实现classSolution{publicint[]searchRange(int[]nums,inttarget){intlolowerBound(nums,target);if(lonums.length||nums[lo]!target){returnnewint[]{-1,-1};}inthilowerBound(nums,target1)-1;returnnewint[]{lo,hi};}privateintlowerBound(int[]nums,inttarget){intlo0,hinums.length-1;while(lohi){intmidlo(hi-lo)/2;// 防溢出 下取整if(nums[mid]target){lomid1;}else{himid;}}// 空数组或 target 大于所有元素if(nums.length0||nums[lo]target){returnnums.length;}returnlo;}}⚠️神级技巧右边界 lower_bound(target 1) - 1对整数数组有效。不用另写upper_bound一行复用。⏱️ 复杂度分析面试必问时间两次二分每次O(logn) →O(logn)空间O(1)仅指针变量 举一反三3 道高频变种题题目变化点应对策略LC.875爱吃香蕉的珂珂二分答案对“吃速”二分判定check(k)是否可行是最经典的二分答案入门LC.33搜索旋转排序数组数组被旋转二分的分界点不再是“值大小”而是判断哪半边有序但循环不变量思想照用LC.4寻找两个正序数组的中位数两个数组 第K小二分答案的巅峰难度对“第K小”做分割点二分 面试追问模拟提前准备Q1为什么普通二分不行非要lower_bound普通二分命中即返回命中位置不确定。lower_bound把“找等于”重构为“找第一个满足 ≥ 的位置”利用单调性精确定位边界。这是二分查找的本质升级。Q2怎么避免死循环三查①hi mid配下取整lo mid配上取整② 每轮确认区间严格缩小③ 选定一套区间定义左闭右闭/左闭右开就全程坚守不要混用。Q3lower_bound和upper_bound的工程应用C有std::lower_bound/upper_boundPython有bisect_left/bisect_rightJava的Arrays.binarySearch找不到时返回-(插入点)-1。三个常用推论① 出现次数 upper_bound - lower_bound② 插入位置 lower_bound③[lower_bound, upper_bound)是 target 的完整区间。Q4“二分答案”是什么当答案 x 满足“判定函数check(x)关于 x 单调”时可以对答案的值域二分而不是对数组下标二分。典型场景“最小化最大值”“最大化最小值”类优化问题LC.875就是代表。 实战小技巧刷题党必备口诀收缩方向定取整himid配下取lomid配上取不变量守护每一轮。模板凡是“找第一个满足条件的位置”闭区间while lo himid (lohi)//2if cond: himid else: lomid1是万能骨架。防坑处理空数组和 target 大于所有元素的边界。 实际应用场景不止是刷题数据库索引B树叶子节点内用二分查找定位记录版本控制git bisect二分查找首个坏commit定时器调度按时间戳检索最近的任务资源调度二分答案找最优阈值限流、扩容、批处理大小 今日思考题如果我们把lower_bound的条件从nums[mid] target改为nums[mid] target这个函数会变成什么提示它会变成upper_bound——第一个 target的位置。你能用这个思路写出一个支持泛型不限于整数的upper_bound吗
