给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路
- 在常规二分查找的逻辑中进行改良
- 命中 target 时，除结果下标外，还返回当前折半的 left, right 下标信息
- 左右两侧分别折半迭代调用 binarySearch 方法进而逼近各自边界信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| var searchRange = function (nums, target) {
const binarySearch = (left, right) => {
while (left <= right) {
const mid = left + Math.floor((right - left) / 2)
if (target < nums[mid]) {
right = mid - 1
} else if (target > nums[mid]) {
left = mid + 1
} else {
return [mid, left, right]
}
}
return [-1, -1, -1]
}
let [keyIndex, _left, _right] = binarySearch(0, nums.length - 1)
if (keyIndex === -1) {
return [-1, -1]
}
let rangeLeft = keyIndex
let rangeRight = keyIndex
{
let left = _left
while (left < rangeLeft) {
const result = binarySearch(left, rangeLeft - 1)
if (result[0] === -1) {
break
}
rangeLeft = result[0]
left = result[1]
}
}
{
let right = _right
while (rangeRight < right) {
const result = binarySearch(rangeRight + 1, right)
if (result[0] === -1) {
break
}
rangeRight = result[0]
right = result[2]
}
}
return [rangeLeft, rangeRight]
}
|