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.

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