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

力扣（在排序数组中查找元素的第一个和最后一个位置）

news 2025/8/23 10:52:33

解析 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置：二分查找的灵活应用

在算法的学习中，LeetCode 34 题要求在排序数组里查找目标元素的起始和结束位置，且需满足 $O(log⁡n)O(\log n)$ 的时间复杂度，这使得二分查找成为解题的关键。以下将详细剖析解题思路、代码逻辑。

一、题目分析

在这里插入图片描述

（一）问题定义

给定非递减排序数组 nums 和目标值 target，找出 target 在数组中的起始索引和结束索引；若不存在，返回 [-1, -1] ，且算法需满足 $O(log⁡n)O(\log n)$ 时间复杂度。

（二）核心挑战

利用二分查找高效定位目标值的边界。因数组有序，常规二分可找目标值，但需改造以精准找第一个和最后一个出现的位置。

二、原代码思路与问题

（一）思路概述

用一个循环，通过 leftKey 标记查找阶段：

查找左边界：leftKey 为 true 时，找到目标值后，更新左边界 topAndDown[0]，并收缩右边界（right = mid - 1 ），继续找更左的目标值。
查找右边界：左边界找到后（left > right 触发），重置 left、right，leftKey 设为 false，再次二分，找到目标值后更新右边界 topAndDown[1]，并收缩左边界（left = mid + 1 ）。

（二）问题

逻辑复杂：通过 left > right 切换查找阶段，增加理解和维护成本，且重置指针易出错。
效率问题：虽整体是 $O(log⁡n)O(\log n)$ ，但代码逻辑不够简洁，可优化为两次独立二分（分别找左、右边界）。

三、优化后的二分查找思路

（一）两次二分法

找左边界：在数组中找第一个大于等于 target 的位置，若该位置值不等于 target，则不存在；否则为左边界。
找右边界：找第一个大于 target 的位置，其前一个位置即为右边界（若存在目标值）。

（二）实现逻辑

左边界查找：初始化 left=0, right=nums.length，二分过程中，若 nums[mid] < target，left = mid + 1；否则 right = mid 。最终 left 即为左边界（需验证是否越界及是否等于 target ）。
右边界查找：初始化 left=0, right=nums.length，二分过程中，若 nums[mid] <= target，left = mid + 1；否则 right = mid 。最终 right - 1 即为右边界（需结合左边界验证）。

四、优化代码实现

class Solution {public int[] searchRange(int[] nums, int target) {int leftBound = findLeftBound(nums, target);// 左边界不存在，直接返回 [-1, -1]if (leftBound == nums.length || nums[leftBound] != target) { return new int[]{-1, -1};}// 右边界是第一个大于 target 位置的前一个int rightBound = findRightBound(nums, target) - 1; return new int[]{leftBound, rightBound};}// 找第一个大于等于 target 的位置（左边界）private int findLeftBound(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return left;}// 找第一个大于 target 的位置（用于推导右边界）private int findRightBound(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid;}}return left;}
}

（一）代码流程

找左边界：调用 findLeftBound，通过二分找到第一个 >= target 的位置。若该位置越界或值不等于 target，直接返回 [-1, -1] 。
找右边界：调用 findRightBound 找到第一个 > target 的位置，其前一个位置即为右边界（因数组有序，若存在目标值，右边界是最后一个 target 的索引）。
返回结果：组合左、右边界，返回最终结果。