Find First and Last Position of Element in Sorted Array

Leetcode Problem 34: Find First and Last Position of Element in Sorted Array

Problem Summary

Given an array of integers sorted in non-decreasing order, find the starting and ending positions of a given target value. If the target is not found, return [-1, -1].

Your algorithm must run in O(log n) time.

Constraints:

• The array has between 0 and 100,000 elements.
• Element values and the target are integers in the range [-1,000,000,000, 1,000,000,000].

Techniques

• Array
• Binary Search

Solution

function searchRange(nums: number[], target: number): number[] {
    let left = 0
    let right = nums.length - 1

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)

        if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        } else {
            let start = mid
            let end = mid

            while (start - 1 >= 0 && nums[start - 1] === target) {
                start--
            }

            while (end + 1 < nums.length && nums[end + 1] === target) {
                end++
            }

            return [start, end]
        }
    }

    return [-1, -1]
}

console.log(searchRange([5,7,7,8,8,10], 8))