Find First and Last Position of Element in Sorted Array medium

Problem Statement

Given a sorted array of integers nums and an integer target, find the starting and ending positions of target in nums. If target is not found, return [-1, -1].

Example 1

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Explanation: The first occurrence of 8 is at index 3 and the last is at index 4.

Example 2

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Explanation: Because 6 does not appear in the array.

Steps

1. Find the first occurrence: Use binary search to find the leftmost index of the target. If the target is found, store the index. If not, the target is not present.

2. Find the last occurrence: Use binary search to find the rightmost index of the target. If the target is found, store the index. If not, the target is not present.

3. Return the result: Return a list containing the first and last occurrences (or [-1, -1] if the target is not found).

Explanation

The solution uses binary search twice – once to find the leftmost occurrence and once to find the rightmost occurrence. Standard binary search finds a position of the target, but we need modifications to find the extremes.

In the search for the leftmost occurrence, if we find the target, we continue searching in the left half to see if there's an earlier occurrence. Similarly, for the rightmost occurrence, if we find the target, we continue searching in the right half.

Code

def searchRange(nums, target):
    """
    Finds the first and last position of a target in a sorted array.

    Args:
        nums: A sorted list of integers.
        target: The integer to search for.

    Returns:
        A list containing the first and last positions of the target, or [-1, -1] if not found.
    """

    def find_first(nums, target):
        left, right = 0, len(nums) - 1
        first = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                first = mid
                right = mid - 1  # Continue searching in the left half
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return first

    def find_last(nums, target):
        left, right = 0, len(nums) - 1
        last = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                last = mid
                left = mid + 1  # Continue searching in the right half
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return last

    first_occurrence = find_first(nums, target)
    if first_occurrence == -1:
        return [-1, -1]
    last_occurrence = find_last(nums, target)
    return [first_occurrence, last_occurrence]

Complexity

• Time Complexity: O(log n) - due to the two binary searches.
• Space Complexity: O(1) - constant extra space is used. The recursive approach can be slightly higher due to stack space, but it's still considered O(1) in practice for typical input sizes.