二分与排序中等1 种解法
#34在排序数组中查找元素的第一个和最后一个位置
在非递减数组中返回 target 的起止下标，不存在时返回 [-1, -1]。
#数组#二分查找
原题
给你一个按照非递减顺序排列的整数数组 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]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
解题主线
- 分别查找第一个不小于 target 和第一个大于 target 的位置，区间即 [lower, upper - 1]。
解法 1：两次下界二分
用统一 lowerBound 分别定位 target 与 target + 1 的边界；为避免 target + 1 溢出，第二次按严格大于查找。
-
时间复杂度： O(log n)
-
空间复杂度： O(1)
final class Solution {
public int[] searchRange(int[] nums, int target) {
int first = lowerBound(nums, target);
// 下界可能落在数组末端，还需确认该位置确实等于 target
if (first == nums.length || nums[first] != target) return new int[] {-1, -1};
int last = upperBound(nums, target) - 1;
return new int[] {first, last};
}
private int lowerBound(int[] nums, int target) {
// 在左闭右开区间中维护：答案始终位于 [left, right]
int left = 0, right = nums.length;
while (left < right) {
int middle = left + (right - left) / 2;
// 小于 target 的位置不可能是下界，连同 middle 一起排除
if (nums[middle] < target) left = middle + 1;
else right = middle;
}
return left;
}
private int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int middle = left + (right - left) / 2;
// upperBound 寻找首个严格大于 target 的位置
if (nums[middle] <= target) left = middle + 1;
else right = middle;
}
return left;
}
}边界与易错点
- lower 可能等于数组长度，读取 nums[lower] 前必须检查。
- 找到一次 target 后不能立即结束，边界仍可能在同侧更远处。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q034_search_first_last.java