Problem
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 <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
Solution
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
var index = findIndex(nums, target);
return index === -1
? [-1, -1]
: [findLeft(nums, target, index), findRight(nums, target, index)];
};
var findIndex = function(nums, target) {
var left = 0;
var right = nums.length - 1;
while (left <= right) {
var mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
};
var findLeft = function(nums, target, index) {
var left = 0;
var right = index;
while (left < right) {
var mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
var findRight = function(nums, target, index) {
var left = index;
var right = nums.length - 1;
while (left < right) {
var mid = left + Math.ceil((right - left) / 2);
if (nums[mid] === target) {
left = mid;
} else {
right = mid - 1;
}
}
return right;
};
Explain:
nope.
Complexity:
- Time complexity : O(log(n)).
- Space complexity : O(1).