34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
题目
Given an array of integers nums
sorted in non-decreasing order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Constraints:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums
is a non-decreasing array.-10^9 <= target <= 10^9
题目大意
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
解题思路
可以使用二分查找分别寻找第一个出现的位置和最后一个出现的位置。
寻找第一个出现的位置(getFirst):
- 使用二分查找。
- 如果
nums[mid] >= target
,则说明第一个目标值可能在mid
或其左侧,调整right = mid - 1
。 - 如果
nums[mid] < target
,则调整left = mid + 1
。 - 查找结束后,检查
left
:- 如果
left
越界或nums[left]
不等于target
,返回-1
; - 其他情况返回
left
。
- 如果
寻找最后一个出现的位置(getLast):
- 同样使用二分查找。
- 如果
nums[mid] > target
,则说明最后一个目标值可能在mid
左侧,调整right = mid - 1
。 - 如果
nums[mid] <= target
,则调整left = mid + 1
。 - 查找结束后,检查
right
:- 如果
right
越界或nums[right]
不等于target
,返回-1
; - 其他情况返回
right
。
- 如果
返回
[getFirst(), getLast()]
。
复杂度分析
时间复杂度:
O(log n)
,其中n
是数组的长度。- 每次调用二分查找的时间复杂度为
O(log n)
,因为在每次迭代中搜索范围缩小一半。 - 总共调用两次二分查找,时间复杂度为
O(2 * log n) = O(log n)
。
- 每次调用二分查找的时间复杂度为
空间复杂度:
O(1)
,算法仅使用常数空间存储变量。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
const getFirst = () => {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
if (left >= nums.length || nums[left] !== target) {
return -1;
}
return left;
};
const getLast = () => {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] <= target) {
left = mid + 1;
}
}
if (right >= nums.length || nums[right] !== target) {
return -1;
}
return right;
};
return [getFirst(), getLast()];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
278 | 第一个错误的版本 | [✓] | 二分查找 交互 | 🟢 | 🀄️ 🔗 |
2055 | 蜡烛之间的盘子 | 数组 字符串 二分查找 1+ | 🟠 | 🀄️ 🔗 | |
2089 | 找出数组排序后的目标下标 | [✓] | 数组 二分查找 排序 | 🟢 | 🀄️ 🔗 |