First and Last Position of Element

Problem Statement

Given a sorted array nums and a target value target, return the starting and ending position of target in the array. If target is not found, return [-1, -1].

Example: nums = [5,7,7,8,8,10], target = 8 → Output: [3,4]

Approach 1: Two Binary Searches

Explanation: Use binary search twice: once to find the first occurrence, once for the last occurrence.

Time Complexity: O(log n)

Space Complexity: O(1)

function findFirst(nums, target):
    low, high = 0, n-1
    first = -1
    while low <= high:
        mid = (low+high)//2
        if nums[mid] == target:
            first = mid
            high = mid - 1
        else if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return first

function findLast(nums, target):
    low, high = 0, n-1
    last = -1
    while low <= high:
        mid = (low+high)//2
        if nums[mid] == target:
            last = mid
            low = mid + 1
        else if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return last

return [findFirst(nums,target), findLast(nums,target)]

Approach 2: Single Pass Modified Binary Search

Explanation: Use a modified binary search to find boundaries efficiently.

Time Complexity: O(log n)

Space Complexity: O(1)

// Similar logic combining first & last in one loop by tracking boundaries

Approach 3: Linear Scan (Naive)

Explanation: Scan array from start to end to find first and last occurrences.

Time Complexity: O(n)

Space Complexity: O(1)

start = -1, end = -1
for i in 0..n-1:
    if nums[i] == target:
        if start == -1:
            start = i
        end = i
return [start, end]