codingpineapple

Posted on

# 34. Find First and Last Position of Element in Sorted Array (javascript solution)

### 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.

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
};
``````