LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置：二分查找实战

刷题路上二分查找是绕不开的经典算法而LeetCode 34题「在排序数组中查找元素的第一个和最后一个位置」正是二分查找的进阶应用——它不仅要求我们找到目标值更要精准定位其在非递减数组中的起始和结束位置同时还要满足O(log n)的时间复杂度要求。今天就来拆解这道题从题干分析到代码实现再到细节坑点一步步搞懂如何高效解决这道题。一、题干解析明确需求与约束先再仔细读一遍题干避免遗漏关键信息输入非递减顺序排列的整数数组nums目标值target输出target在数组中的开始位置和结束位置若不存在则返回[-1, -1]核心约束必须设计时间复杂度为O(log n)的算法。这里有两个关键点需要注意非递减数组数组元素可能重复且从左到右不递减允许相等这是二分查找的前提也是我们定位边界的核心依据O(log n)时间复杂度直接遍历数组O(n)会超时因此必须用二分查找且需要两次二分——分别找左边界第一个等于target的位置和右边界最后一个等于target的位置。二、解题思路两次二分查找定位左右边界既然数组是有序的我们可以利用二分查找的特性通过调整判断条件分别找到target的左边界和右边界左边界第一个大于等于target的位置如果target存在这个位置就是第一个target的索引如果不存在这个位置会大于数组长度或对应元素不等于target右边界第一个大于target的位置再减1如果target存在减1后就是最后一个target的索引如果不存在减1后会小于左边界。为了复用代码我们可以设计一个通用的二分查找函数通过一个布尔参数lower来控制查找左边界还是右边界当lower为true时查找左边界第一个target的位置当lower为false时查找右边界的“临界位置”第一个target的位置。最后通过判断左边界是否小于等于右边界、且边界对应的元素是否为target来确定最终结果——如果满足则返回[左边界, 右边界]否则返回[-1, -1]。三、代码实现与逐行解析先给出完整代码TypeScript版本再逐行拆解核心逻辑确保每一步都能理解functionsearchRange(nums:number[],target:number):number[]{constnnums.length;// 通用二分查找函数lower控制查找左边界/右边界临界值constbinarySearch(target:number,lower:boolean){letleft0,rightn-1,ansn;// ans初始化为n应对target大于所有元素的情况while(leftright){constmidMath.floor((leftright)/2);// 中间位置避免溢出// 关键判断根据lower调整二分方向if(nums[mid]target||(lowernums[mid]target)){rightmid-1;// 目标在左半区收缩右边界ansmid;// 记录当前mid可能是我们要找的边界}else{leftmid1;// 目标在右半区收缩左边界}}returnans;}letres:number[][-1,-1];// 初始化为不存在的情况constleftIdxbinarySearch(target,true);// 查找左边界constrightIdxbinarySearch(target,false)-1;// 查找右边界并调整// 验证边界的合法性左边界右边界且边界元素等于targetif(leftIdxrightIdxrightIdxnums.lengthnums[leftIdx]targetnums[rightIdx]target){res[leftIdx,rightIdx];}returnres;};核心代码逐行解析1. 初始化与通用二分函数定义const n nums.length; —— 记录数组长度避免多次调用nums.length提升效率。binarySearch函数接收target和lower两个参数返回对应边界的索引。这里ans初始化为n是为了应对target大于数组中所有元素的情况此时二分结束后ans仍为n后续rightIdx n-1会小于leftIdx直接返回[-1,-1]。2. 二分查找的核心判断逻辑if (nums[mid] target || (lower nums[mid] target))这是整个算法的灵魂分两种情况理解当lower为true找左边界只要nums[mid] target就说明左边界可能在mid或mid左侧因此收缩右边界right mid - 1并记录当前mid为候选边界ans mid当lower为false找右边界临界值只有nums[mid] target时才说明右边界临界值在mid或mid左侧收缩右边界否则继续向右查找。else { left mid 1; }当不满足上述条件时说明目标在mid右侧收缩左边界继续查找。3. 边界验证与结果返回leftIdx binarySearch(target, true)得到左边界第一个target的位置rightIdx binarySearch(target, false) - 1得到第一个target的位置减1后就是最后一个target的位置即右边界边界验证条件leftIdx rightIdx确保边界有效不会出现左边界在右边界右侧的情况、rightIdx nums.length避免数组越界、nums[leftIdx] target和nums[rightIdx] target确保找到的边界确实是target的位置而非其他值的边界。四、关键坑点与注意事项这道题看似简单但很多人在二分查找的边界处理上容易出错总结几个高频坑点ans的初始值必须设为n而不是-1。如果target大于数组中所有元素二分结束后left会超过rightans仍为n此时rightIdx n-1leftIdx nleftIdx rightIdx直接返回[-1,-1]避免出错二分循环条件必须是left right而不是left right。如果用left right可能会错过最后一个符合条件的元素比如数组中只有一个target时边界验证不能只判断leftIdx rightIdx还要验证nums[leftIdx]和nums[rightIdx]是否等于target。比如数组为[1,2,3,4]target为5此时leftIdx 4rightIdx 3不满足leftIdx rightIdx但如果target为0leftIdx 0rightIdx -1也不满足如果数组为[2,2]target为3leftIdx 2rightIdx 1同样不满足整数溢出mid的计算用Math.floor((left right) / 2)在JavaScript/TypeScript中整数范围足够大不会出现溢出但如果是其他语言如Java建议用left Math.floor((right - left)/2)避免leftright溢出。五、总结与拓展这道题的核心是「二分查找的边界定位」通过一次二分查找函数的复用分别找到左、右边界既满足了O(log n)的时间复杂度又简化了代码逻辑。拓展思考如果数组是递减的如何修改代码只需调整二分查找的判断条件将nums[mid] target改为nums[mid] target即可如果题目要求找到target的出现次数只需用右边界 - 左边界 1若存在target否则为0二分查找的核心是「收缩边界」只要明确“目标在左半区还是右半区”就能灵活调整判断条件解决各类边界查找问题。