Naive Solution

A brute force solution would involve iterating through the array and checking each element to see if it matches the target. If a match is found, we record the index. We continue iterating to find the first and last occurrences.

Code

def search_range_brute_force(nums, target):
    first = -1
    last = -1
    for i in range(len(nums)):
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    return [first, last]

Time Complexity

O(n), where n is the number of elements in the array.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Solution

Since the array is sorted, we can use binary search to find the first and last occurrences of the target value. This will give us a time complexity of O(log n).

Algorithm

1. Find the first occurrence:
   • Perform binary search to find the target.
   • If the target is found, check if it's the first occurrence (i.e., nums[mid - 1] != target or mid == 0).
   • If it's not the first occurrence, search in the left half.
2. Find the last occurrence:
   • Perform binary search to find the target.
   • If the target is found, check if it's the last occurrence (i.e., nums[mid + 1] != target or mid == len(nums) - 1).
   • If it's not the last occurrence, search in the right half.

Code

def search_range(nums, target):
    def find_first(nums, target):
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
            if nums[mid] == target:
                index = mid
        return index

    def find_last(nums, target):
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
            if nums[mid] == target:
                index = mid
        return index

    first = find_first(nums, target)
    last = find_last(nums, target)
    return [first, last]

Time Complexity

O(log n), because we perform two binary searches.

Space Complexity

O(1), as we only use a constant amount of extra space.

Edge Cases

• Empty array: Return [-1, -1]. The code handles this case correctly.
• Target is not found: Return [-1, -1]. The binary search returns -1 if the target is not found.
• Target is at the beginning or end of the array: The algorithm correctly identifies the boundaries.
• Array with a single element that matches the target: The algorithm correctly identifies the start and end as the same index.