34. 在排序数组中查找元素的第一个和最后一个位置
查看题目中等
数组
排序
中频
解法一：二分查找
时间复杂度：O(log n) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 输入排序数组和目标值，然后点击开始
代码实现
// JAVA 代码待补充时间复杂度：O(log n)
空间复杂度：O(1)
## 解题思路
1. **问题分析**：
- 给定一个排序数组和一个目标值，要求找到该目标值在数组中的第一个和最后一个位置
- 如果目标值不存在于数组中，返回 [-1, -1]
2. **算法选择**：
- 使用二分查找算法，因为数组是排序的，二分查找的时间复杂度为 O(log n)，比线性查找更高效
- 需要实现两个二分查找，分别寻找左边界和右边界
3. **核心思想**：
- **寻找左边界**：当找到目标值时，继续向左搜索，直到找到第一个出现的位置
- **寻找右边界**：当找到目标值时，继续向右搜索，直到找到最后一个出现的位置
4. **实现细节**：
- 使用一个通用的 binarySearch 函数，通过 lower 参数控制是寻找左边界还是右边界
- 当 lower 为 true 时，寻找左边界（第一个大于等于 target 的位置）
- 当 lower 为 false 时，寻找右边界（第一个大于 target 的位置减 1）
- 最后验证找到的左右边界是否有效（是否在数组范围内且值等于 target）
5. **时间复杂度**：
- 二分查找的时间复杂度为 O(log n)，执行两次二分查找，总时间复杂度仍为 O(log n)
6. **空间复杂度**：
- 只使用常数级别的额外空间，空间复杂度为 O(1)
## 适用场景
- 适用于已排序数组中查找元素的范围
- 适用于需要快速定位元素在排序数组中出现的起始和结束位置的场景
- 特别适合处理可能包含重复元素的排序数组