问题描述
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 (opens in a new tab)，难度中等。
给你一个按照非递减顺序排列的整数数组 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 <= 10^5-10^9 <= nums[i] <= 10^9nums是一个非递减数组-10^9 <= target <= 10^9
题解
题解：借助快排的思想。
Solution.java
class Solution {
public int[] searchRange(int[] nums, int target) {
// 初始化
int[] result = new int[]{-1, -1};
int left = 0, right = nums.length - 1, mid = (left + right) / 2;
while (left <= right) {
if (nums[mid] == target) {
result = new int[]{mid, mid};
// 寻找 target 在 nums 的左右边界
int t = mid;
// 判断 --t 是否越界
while (t - 1 >= 0 && nums[--t] == target) {
result[0] = t;
}
int k = mid;
// 判断 ++k 是否越界
while (k + 1 < nums.length && nums[++k] == target) {
result[1] = k;
}
break;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
mid = (left + right) / 2;
}
return result;
}
}