.jpg)
816 字
4 分钟
排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
解题思路
- 二分查找变形：
- 使用两次二分查找分别定位起始和结束位置
- 第一次查找左边界：当
nums[mid] == target时继续向左搜索 - 第二次查找右边界：当
nums[mid] == target时继续向右搜索
- 边界条件处理：
- 查找左边界后验证有效性
- 若左边界无效则直接返回 [-1, -1]
- 优化终止条件：
- 左边界找到后，右边界查找只需从左边界开始
- 减少无效搜索区域
- 二分模板统一：
- 循环条件
while (low <= high)确保完整覆盖 - 中点计算避免溢出：
mid = low + ((high - low) >> 1)
- 循环条件
关键洞察
- 边界分离原理：
- 起始和结束位置需要独立查找
- 标准二分查找无法同时获取两端边界
- 查找策略差异：
- 左边界优先考虑左侧区域（收缩右边界）
- 右边界优先考虑右侧区域（收缩左边界）
- 顺序依赖特性：
- 右边界查找可基于左边界结果优化
- 减少约50%搜索范围
- 无效结果处理：
- 左边界无效时直接返回失败
- 避免无效的右边界搜索
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(log n)：两次二分查找 |
| 空间复杂度 | O(1)：仅使用指针变量 |
代码实现
/** * @param {number[]} nums * @param {number} target * @return {number[]} */var searchRange = function (nums, target) { const search = (nums, target, leftRight) => { let ans = -1; let left = 0, right = nums.length - 1; while (left <= right) { const middle = left + Math.floor((right - left) / 2); if (nums[middle] === target) { ans = middle; leftRight ? right = middle - 1 : left = middle + 1; } else if (nums[middle] < target) { left = middle + 1; } else { right = middle - 1; } }
return ans; } return [ search(nums, target, true), search(nums, target, false) ]};变种：单次遍历实现
const searchRangeOptimized = (nums, target) => { let left = -1, right = -1; let low = 0, high = nums.length - 1;
while (low <= high) { const mid = low + ((high - low) >> 1); if (nums[mid] < target) { low = mid + 1; } else if (nums[mid] > target) { high = mid - 1; } else { // 找到目标时向两侧扩展 left = right = mid; while (left > 0 && nums[left - 1] === target) left--; while (right < nums.length - 1 && nums[right + 1] === target) right++; return [left, right]; } }
return [left, right];};// 时间复杂度：最坏O(n)（全相同元素时）实际应用场景
- 日志时间范围查询：在有序时间戳中查找特定事件的首次和末次发生时间`
- 数据库索引检索：B+树索引中定位索引键的起始位置`
- 基因位置定位： DNA序列中查找特定碱基序列的起止位置`
- 版本控制系统： 提交历史中定位特定修改的首次和末次出现`