当前位置：首页 > news >正文

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

news 2026/3/27 7:28:39

刷题路上，二分查找是绕不开的经典算法，而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[]{constn=nums.length;// 通用二分查找函数：lower控制查找左边界/右边界临界值constbinarySearch=(target:number,lower:boolean)=>{letleft=0,right=n-1,ans=n;// ans初始化为n，应对target大于所有元素的情况while(left<=right){constmid=Math.floor((left+right)/2);// 中间位置，避免溢出// 关键判断：根据lower调整二分方向if(nums[mid]>target||(lower&&nums[mid]>=target)){right=mid-1;// 目标在左半区，收缩右边界ans=mid;// 记录当前mid，可能是我们要找的边界}else{left=mid+1;// 目标在右半区，收缩左边界}}returnans;}letres:number[]=[-1,-1];// 初始化为不存在的情况constleftIdx=binarySearch(target,true);// 查找左边界constrightIdx=binarySearch(target,false)-1;// 查找右边界并调整// 验证边界的合法性：左边界<=右边界，且边界元素等于targetif(leftIdx<=rightIdx&&rightIdx<nums.length&&nums[leftIdx]===target&&nums[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会超过right，ans仍为n，此时rightIdx = n-1，leftIdx = n，leftIdx > rightIdx，直接返回[-1,-1]，避免出错；
二分循环条件：必须是left <= right，而不是left < right。如果用left < right，可能会错过最后一个符合条件的元素（比如数组中只有一个target时）；
边界验证：不能只判断leftIdx <= rightIdx，还要验证nums[leftIdx]和nums[rightIdx]是否等于target。比如数组为[1,2,3,4]，target为5，此时leftIdx = 4，rightIdx = 3，不满足leftIdx <= rightIdx；但如果target为0，leftIdx = 0，rightIdx = -1，也不满足；如果数组为[2,2]，target为3，leftIdx = 2，rightIdx = 1，同样不满足；
整数溢出：mid的计算用Math.floor((left + right) / 2)，在JavaScript/TypeScript中，整数范围足够大，不会出现溢出，但如果是其他语言（如Java），建议用left + Math.floor((right - left)/2)，避免left+right溢出。