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)
的算法解决此问题。
解题思路
可以通过两次二分查找来完成这个过程。
首先,定义一个辅助函数 findFirst
,用于找到目标值的起始位置。这个函数使用二分查找的方法,在每一步查找中,如果中间元素大于等于目标值,将right
指针移动到中间位置的左边,并更新结果为当前中间位置。如果中间元素小于目标值,将left
指针移动到中间位置的右边。
类似地,定义另一个辅助函数 findLast
,用于找到目标值的结束位置。这个函数也使用二分查找的方法,但是在每一步查找中,如果中间元素小于等于目标值,将left
指针移动到中间位置的右边,并更新结果为当前中间位置。如果中间元素大于目标值,将right
指针移动到中间位置的左边。
最终,调用这两个辅助函数得到目标值的起始位置和结束位置,返回结果数组 [start, end]
。
这样,就能够通过两次二分查找,找到目标值在有序数组中的起始位置和结束位置。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
const getFirst = (nums, target) => {
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 = (nums, target) => {
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(nums, target), getLast(nums, target)];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
278 | 第一个错误的版本 | [✓] | 二分查找 交互 | 🟢 | 🀄️ 🔗 |
2055 | 蜡烛之间的盘子 | 数组 字符串 二分查找 1+ | 🟠 | 🀄️ 🔗 | |
2089 | 找出数组排序后的目标下标 | 数组 二分查找 排序 | 🟢 | 🀄️ 🔗 |