在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
codeType
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
codeType
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
codeType
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
解法
只需要用两次二分查找，分别查找目标值的左边界和右边界即可
ts
function searchRange(nums: number[], target: number): number[] {
// 目标值可以用二分查找直接找到
// 问题在于如何找到目标值的边界
// （如果是逐个找，最坏的情况下时间复杂度会变成O(n)）
let ans = [-1, -1]
// 可以直接用二分查找找左边界和右边界
// 找到目标值以后要加一个判断，比如左边界的左边一位和其值不等
const n = nums.length
let low = 0, high = n - 1
// 查找左边界
while(low <= high){
let mid = Math.floor((low + high) / 2)
if(nums[mid] === target && nums[mid - 1] !== target){
// 找到左边界
ans[0] = mid
break;
}
if(nums[mid] >= target){
// 左边界在mid左边
high = mid - 1
}else{
// 左边界在mid右边
low = mid + 1
}
}
// 没找到左边界
if(ans[0] === -1) return ans
// 查找右边界
low = 0, high = n - 1
while(low <= high){
let mid = Math.floor((low + high) / 2)
if(nums[mid] === target && nums[mid + 1] !== target){
// 右边界
ans[1] = mid
}
if(nums[mid] <= target){
// 右边界在右边
low = mid + 1
}else{
// 右边界在左边
high = mid - 1
}
}
return ans
};