企业官网建设流程全解析

二分查找堪称算法界的“翻车之王”——《编程珠玑》里Jon Bentley曾统计，专业程序员中能一次写对二分查找的不到 10%。

边界条件、死循环、溢出、漏解……坑比代码多。

更恶心的是，普通的二分查找只能找到“某个”target，而面试最爱考的是：

有重复元素时，找第一个和最后一个target。

LeetCode34这道题，就是专门用来治你“二分边界强迫症”的。

今天我们用一套循环不变量方法，一次写对lower_bound和upper_bound，从此告别死循环。

顺带解锁高阶技能——二分答案。

📦 题目速览（30 秒读懂）

给定一个非递减数组nums和目标值target，找出target在数组中的第一个和最后一个位置。不存在则返回[-1, -1]。

示例：nums = [5,7,7,8,8,10],target=8→ 输出[3,4]
示例：target=6→ 输出[-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]及其左边全部不满足条件，[hi+1]及其右边全部满足条件
——答案永远藏在[lo, hi]里。

• 如果nums[mid] < target→ mid及左边都不满足 →lo = mid + 1
• 如果nums[mid] >= target→ mid满足（可能是答案）→hi = mid（保留 mid）

循环结束于lo == hi，此时lo就是第一个满足条件的位置。

死循环是怎么来的？

• hi = mid时，mid必须下取整（(lo+hi)//2），否则lo, hi相邻时mid=lo，lo=mid会导致原地踏步。
• lo = mid时，mid必须上取整（(lo+hi+1)//2），否则同样会死循环。

一句话口诀：收缩方向和取整方向必须错开，保证每轮区间严格缩小。

🖼️ 图解算法（手把手走一遍）

nums = [5,7,7,8,8,10],target = 8，求lower_bound(8)（第一个 ≥ 8）：

求upper_bound(8)（第一个 > 8），条件换成nums[mid] > 8：

最后一个 8 的位置 = 5 - 1 =4。最终[3,4]✅

💻 代码实现（Python + Java）

Python 版（最优雅写法）

classSolution:defsearchRange(self,nums:List[int],target:int)->List[int]:lo=self.lower_bound(nums,target)# 不存在的情况：越界或值不相等iflo==len(nums)ornums[lo]!=target:return[-1,-1]hi=self.lower_bound(nums,target+1)-1# 右边界！巧妙！return[lo,hi]deflower_bound(self,nums,target):"""返回第一个 >= target 的下标（C++ lower_bound 语义）"""lo,hi=0,len(nums)-1whilelo<hi:# 区间非空mid=(lo+hi)//2# 下取整，配合 hi=midifnums[mid]<target:lo=mid+1# mid 不满足，排除else:hi=mid# mid 满足，保留候选iflen(nums)==0ornums[lo]<target:returnlen(nums)returnlo# lo == hi，收敛

Java 版（完整实现）

classSolution{publicint[]searchRange(int[]nums,inttarget){intlo=lowerBound(nums,target);if(lo==nums.length||nums[lo]!=target){returnnewint[]{-1,-1};}inthi=lowerBound(nums,target+1)-1;returnnewint[]{lo,hi};}privateintlowerBound(int[]nums,inttarget){intlo=0,hi=nums.length-1;while(lo<hi){intmid=lo+(hi-lo)/2;// 防溢出 + 下取整if(nums[mid]<target){lo=mid+1;}else{hi=mid;}}// 空数组或 target 大于所有元素if(nums.length==0||nums[lo]<target){returnnums.length;}returnlo;}}

⚠️神级技巧：右边界 =lower_bound(target + 1) - 1（对整数数组有效）。不用另写upper_bound，一行复用。

⏱️ 复杂度分析（面试必问）

• 时间：两次二分，每次O(logn) →O(logn)
• 空间：O(1)（仅指针变量）

🚀 举一反三：3 道高频变种题

💬 面试追问模拟（提前准备）

Q1：为什么普通二分不行，非要lower_bound？

普通二分命中即返回，命中位置不确定。lower_bound把“找等于”重构为“找第一个满足 ≥ 的位置”，利用单调性精确定位边界。这是二分查找的本质升级。

Q2：怎么避免死循环？

三查：

①hi = mid配下取整，lo = mid配上取整；

② 每轮确认区间严格缩小；

③ 选定一套区间定义（左闭右闭/左闭右开）就全程坚守，不要混用。

Q3：lower_bound和upper_bound的工程应用？

C++有std::lower_bound/upper_bound，

Python有bisect_left/bisect_right，

Java的Arrays.binarySearch找不到时返回-(插入点)-1。

三个常用推论：

① 出现次数 =upper_bound - lower_bound；

② 插入位置 =lower_bound；

③[lower_bound, upper_bound)是 target 的完整区间。

Q4：“二分答案”是什么？

当答案 x 满足“判定函数check(x)关于 x 单调”时，可以对答案的值域二分，而不是对数组下标二分。

典型场景：“最小化最大值”“最大化最小值”类优化问题，LC.875就是代表。

🧩 实战小技巧（刷题党必备）

• 口诀：收缩方向定取整，hi=mid配下取，lo=mid配上取；不变量守护每一轮。
• 模板：凡是“找第一个满足条件的位置”，闭区间while lo < hi+mid = (lo+hi)//2+if cond: hi=mid else: lo=mid+1是万能骨架。
• 防坑：处理空数组和 target 大于所有元素的边界。

📈 实际应用场景（不止是刷题）

• 数据库索引：B+树叶子节点内用二分查找定位记录
• 版本控制：git bisect二分查找首个坏commit
• 定时器调度：按时间戳检索最近的任务
• 资源调度：二分答案找最优阈值（限流、扩容、批处理大小）

🎁 今日思考题

如果我们把lower_bound的条件从nums[mid] < target改为nums[mid] <= target，这个函数会变成什么？
提示：它会变成upper_bound——第一个> target的位置。

你能用这个思路写出一个支持泛型（不限于整数）的upper_bound吗？