Description:
You are given a string s and an integer k. You can Given an array of integers nums sorted in ascending 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.
Solution:
Time Complexity : O(nlog(n))
Space Complexity: O(1)
var searchRange = function(nums, target) {
const output = []
// find lower bounds
let l1 = 0, r1 = nums.length;
while(l1 < r1) {
const mid = l1 + Math.floor((r1-l1)/2)
if(nums[mid] >= target) r1 = mid
else l1 = mid+1
}
// if we can't find target in the array then return [-1,-1]
if(nums[l1]!==target) return [-1,-1]
// if we did find target, push the lower bound into the output array and search for the upper bound index
output.push(l1)
// find upper bounds
let l2 = l1, r2 = nums.length;
while(l2 < r2) {
const mid = l2 + Math.floor((r2-l2)/2)
if(nums[mid] <= target) l2 = mid+1
else r2 = mid
}
// pointers will meet at the index above the upper bound index, push in the index 1 less than where they meet
output.push(l2-1)
return output
};
Top comments (0)