34. Find First and Last Position of Element in Sorted Array
34. Find First and Last Position of Element in Sorted Array
题目
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. 第一个错误的版本](./0278.md)
- [2055. 蜡烛之间的盘子](https://leetcode.com/problems/plates-between-candles)
- [2089. 找出数组排序后的目标下标](https://leetcode.com/problems/find-target-indices-after-sorting-array)