leetcode 34题 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 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]
思路
二分法，通过找到第一个等于target的值和找到最后一个等于target的值，即是所求。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
// 二分搜索变种题（找到第一个等于target的值，找到最后一个等于target的值）
return [findFirstEqualElement(nums, target), findLastEqualElement(nums, target)];
};
function findFirstEqualElement(nums, target) {
let low = 0, high = nums.length - 1;
while (low <= high) {
const mid = low + (high - low) / 2 | 0;
if (nums[mid] > target) {
high = mid - 1;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
if (mid === 0 || nums[mid-1] !== target) {
return mid;
}
high = mid - 1;
}
}
return -1;
}
function findLastEqualElement(nums, target) {
let low = 0, high = nums.length - 1;
while (low <= high) {
const mid = (high - low) / 2 | 0 + low;
if (nums[mid] > target) {
high = mid - 1;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
if (nums[mid + 1] !== target || mid === nums.length - 1) {
return mid;
}
low = mid + 1;
}
}
return -1;
}
const searchRange = (nums, target) => {
if (nums.length === 0) {
return [-1, -1];
}
let low = 0, high = nums.length - 1;
let start = 0, end = 0;
while (low <= high) {
const mid = ((high - low) / 2 | 0) + low;
if (nums[mid] === target) {
start = mid;
end = mid;
while (start > low && nums[start - 1] === nums[start]) {
start--;
}
while (end < high && nums[end+1] === nums[end]) {
end++;
}
return [start, end];
} else if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return [-1, -1];
};
复杂度分析:
- 时间复杂度: O(logN)
- 空间复杂度：O(1)