DSA: Find First and Last Position of Element in Sorted Array

Matthew Golden

— 2 min read
DSA: Find First and Last Position of Element in Sorted Array

A solution to Leetcode #34, Find First and Last Position of Element in Sorted Array

Problem Statement: Given an array of integers nums sorted in non-decreasing 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.

We know the array is sorted and non-decreasing, meaning each value is greater than or equal to its previous value. Binary Search will provide an O(log n) solution. In general, the iterative solution looks like this:

def binary_search(nums: List[int], target: int) -> int:  
    low = 0  
    high = len(nums) - 1  
    while low <= high:  
        mid = low + (high - low) // 2  
        if nums[mid] == target:  
            return mid  
        elif nums[mid] < target:  
            low = mid + 1  
        elif nums[mid] > target:  
            high = mid - 1  
    return -1

The search interval [low, high] is repeatedly divided in half until the target is found. This implementation returns the index of the first value found. It needs to be modified to produce an upper and lower bound for a target value.

Let's modify this binary_search function to find the lower bound for a target's location in the array:

def lower_bound(nums: List[int], target: int) -> int:  
    low = 0  
    high = len(nums) - 1  
    min_index = -1  
    while low <= high:  
        mid = low + (high - low) // 2  
        if nums[mid] == target:  
            min_index = mid  
            high = mid - 1  
        elif nums[mid] < target:  
            low = mid + 1  
        elif nums[mid] > target:  
            high = mid - 1  
    return min_index

Not much has changed. We add a variable to track the min index value. Then when a target value is found, the search interval is modified by setting the high variable to one less than the mid index. If another value matching the target is found in the new interval, min_index is updated with the new location. We only had to add two lines of code.

Likewise, we can modify binary_search to find the upper bound for a target's location:

def upper_bound(nums: List[int], target: int) -> int:  
    low = 0  
    high = len(nums) - 1  
    max_index = -1  
    while low <= high:  
        mid = low + (high - low) // 2  
        if nums[mid] == target:  
            max_index = mid  
            low = mid + 1  
        elif nums[mid] < target:  
            low = mid + 1  
        elif nums[mid] > target:  
            high = mid - 1  
    return max_index

Notice the only difference between lower_bound and upper_bound is how the search interval is updated when a target value is found. Instead of maintaining separate upper_bound and lower_bound functions, the update logic can be passed to our search algorithm as lambdas.

def searchRange(nums: List[int], target: int) -> List[int]:  
    lower = lambda low, high, mid: (low, mid - 1)  
    upper = lambda low, high, mid: (mid + 1, high)  
    return [determine_bound(nums, target, lower), determine_bound(nums, target, upper)]  
  
  
def determine_bound(nums: list[int], target: int, update: Callable[[int, int], int]) -> int:  
    low = 0  
    high = len(nums) - 1  
    index = -1  
    while low <= high:  
        mid = low + (high - low) // 2  
        if nums[mid] == target:  
            index = mid  
            low, high = update(low, high, mid)  
        elif nums[mid] < target:  
            low = mid + 1  
        elif nums[mid] > target:  
            high = mid - 1  
    return index

Read more