【LeetCode 刷题笔记】34. 在排序数组中查找元素的第一个和最后一个位置 | 二分查找经典刷题题解

一、题目描述给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。示例 1:输入: nums [5,7,7,8,8,10], target 8输出: [3,4]示例 2:输入: nums [5,7,7,8,8,10], target 6输出: [-1,-1]示例 3:输入: nums [], target 0输出: [-1,-1]二、解题思路题目明确要求时间复杂度为O(log n)暴力遍历O(n)不符合要求必须使用二分查找。核心需求拆解找到目标值的左边界第一个等于target的位置和右边界最后一个等于target的位置。优化思路复用同一个“找下界”的二分函数避免写两套逻辑1. 左边界直接调用lowBound(nums, target)得到第一个大于等于target的索引2. 右边界调用lowBound(nums, target 1)得到第一个大于等于target1的索引再减1即为最后一个等于target的索引3. 先判断左边界是否有效是否存在target不存在则直接返回[-1,-1]。三、代码实现Javaclass Solution {public int[] searchRange(int[] nums, int target) {// 1. 找目标值的左边界第一个等于target的位置int start lowBound(nums, target);// 2. 判断目标值是否存在左边界超出数组或对应元素不等于target说明不存在if (start nums.length || nums[start] ! target) {return new int[]{-1, -1};}// 3. 找右边界找target1的下界再减1即为最后一个等于target的位置int end lowBound(nums, target 1) - 1;return new int[]{start, end};}/*** 找数组中第一个大于等于target的元素的索引下界函数* param nums 非递减排序数组* param target 目标值* return 第一个大于等于target的索引不存在则返回nums.length*/public int lowBound(int[] nums, int target) {int left 0;int right nums.length - 1;int mid 0;// 闭区间二分查找保证遍历所有元素while (left right) {// 计算中间位置避免low high直接相加导致int溢出mid left (right - left) / 2;if (nums[mid] target) {// mid值大于等于target左边界在左侧含mid更新右边界right mid - 1;} else {// mid值小于target左边界在右侧不含mid更新左边界left mid 1;}}// 循环结束时left即为第一个大于等于target的位置return left;}}四、核心笔记 易错点解析1. 二分查找中“等于”情况的合并逻辑- 正常二分查找中若nums[mid] target需要向左查找right mid - 1- 在找下界第一个大于等于target的位置时nums[mid] target也需要向左查找因为左侧可能存在更小的索引等于target因此将与的情况合并处理统一更新right mid - 1- 若要找上界最后一个等于target的位置则nums[mid] target需要向右查找此时应与的情况合并更新left mid 1- 无需死记硬背“等于和谁合并”只需根据找上下界的需求确定时该往哪个方向缩小区间再合并即可。2. 目标值不存在的三种情况分析调用lowBound函数后若目标值不在数组中会出现三种情况- 数组所有元素都小于target此时left nums.length超出数组范围right nums.length - 1需通过start nums.length判断不存在- 数组所有元素都大于target此时left 0但nums[left] ! target需通过nums[start] ! target判断不存在- 数组中部分元素小于target、部分大于target此时right是小于target的最大值的索引left是大于target的最小值的索引同样通过nums[start] ! target判断不存在因此调用lowBound后必须加上start nums.length || nums[start] ! target的判断才能确定target是否存在。3. 循环结束的边界特性由于while (left right)的循环条件无论与谁合并在一起循环结束时一定满足right left且right 1 left- 若target存在于数组中left是目标值的下界right是小于target的最大元素的索引- 若target不存在left是target应该插入的位置right是小于target的最大元素的索引这个特性是后续计算右边界lowBound(nums, target 1) - 1的核心依据。五、复杂度分析-时间复杂度O(log n)两次调用lowBound函数每次都是二分查找时间复杂度为O(log n)两次调用仍为O(log n)符合题目要求。-空间复杂度O(1)仅使用了常数级别的额外变量没有使用额外的辅助空间。六、总结- 这道题的核心是利用“找下界”的二分函数同时解决目标值左右边界的查找问题避免了写两套二分逻辑代码更简洁易维护。- 关键在于理解二分查找中情况的合并逻辑以及循环结束后left和right的边界特性。- 必须先判断目标值是否存在再计算右边界避免数组越界或返回错误结果。