Find First and Last Position of Element in Sorted Array (M)
题目
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
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]
题意
在给定的递增数组中找到目标值出现的第一个位置和最后一个位置，未找到目标值则返回[-1, -1]。
思路
查找第一个位置时，通过二分法找到目标值后，先向左递归看左侧是否仍存在目标值，存在则返回递归值，不存在则返回当前值；同理可查找最后一个位置。
代码实现
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
// 当不存在目标值时，必然有 first = last = -1
int first = binarySearch(nums, 0, nums.length - 1, target, true);
int last = first == -1 ? -1 : binarySearch(nums, 0, nums.length - 1, target, false);
return new int[]{first, last};
}
private int binarySearch(int[] nums, int left, int right, int target, boolean findLeft) {
while (left <= right) {
int mid = (left + right) / 2;
if (target < nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
int value;
// 每次先判断在左/右侧是否仍存在目标值
if (findLeft) {
value = binarySearch(nums, left, mid - 1, target, true);
} else {
value = binarySearch(nums, mid + 1, right, target, false);
}
return value == -1 ? mid : value;
}
}
return -1;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let left = 0, right = nums.length - 1
let res = []
// 找出现的第一个位置
while (left < right) {
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] === target) {
right = mid
} else if (nums[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
if (nums[left] !== target) {
return [-1, -1]
}
res.push(left)
// 找出现的最后一个位置
left = 0, right = nums.length
while (left < right) {
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] > target) {
right = mid
} else {
left = mid + 1
}
}
res.push(left - 1)
return res
}