给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 $O(log n)$ 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
二分查找
数组是有序的，所以查找目标值可以使用二分查找，只需要在找到目标值后再左右查找到开始位置和结束位置即可。
具体的实现如下：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const searchRange1 = function(nums, target) {
let [left, right, middle] = [0, nums.length - 1];
while (left <= right) {
middle = Math.floor((left + right) / 2);
// 二分查找找到了target
if (nums[middle] === target) {
// 分别向左和向右寻找开始位置及结束位置
let [resultLeft, resultRight] = [middle, middle];
while (nums[resultLeft] === target) {
resultLeft --;
}
while (nums[resultRight] === target) {
resultRight ++;
}
return [resultLeft + 1, resultRight - 1];
}
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return [-1, -1];
};
测试：
let start = new Date();
const test = searchRange1;
console.log(test([5,7,7,8,8,10], 8)); // [ 3, 4 ]
console.log(test([5,7,7,8,8,10], 6)); // [ -1, -1 ]
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 正常情况下时间复杂度为$O(logn)$，但在$target$重复次数较多时性能会下降，最差情况下时间复杂度为$O(n)$
空间复杂度： 空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 6,2019