Naive Solution

A brute-force approach to solve this problem would involve iterating through the array nums and checking each element to see if it matches the target value. If a match is found, we continue iterating to find the first and last occurrences.

Algorithm:

1. Initialize start and end to -1.
2. Iterate through the array nums from the beginning.
3. If nums[i] equals target, then:
   • If start is -1, set start to i.
   • Set end to i.
4. After the loop, return [start, end].

Code (Python):

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

Time and Space Complexity:

• Time Complexity: O(n), where n is the number of elements in the array, as we iterate through the array once.
• Space Complexity: O(1), as we use a constant amount of extra space.

Optimal Solution (Binary Search)

Since the array is sorted, we can use binary search to find the target value. To find the starting and ending positions, we can perform two binary searches:

1. One to find the leftmost (first) occurrence of the target.
2. Another to find the rightmost (last) occurrence of the target.

Algorithm:

1. Find the Leftmost Occurrence:
   • Initialize left to 0 and right to len(nums) - 1.
   • While left <= right:
     • Calculate mid = left + (right - left) // 2.
     • If nums[mid] == target:
       • Update end to mid
       • Move right = mid - 1 to find if there is any other occurence on the left side
     • If nums[mid] < target:
       • Move left = mid + 1.
     • Else:
       • Move right = mid - 1.
2. Find the Rightmost Occurrence:
   • Initialize left to 0 and right to len(nums) - 1.
   • While left <= right:
     • Calculate mid = left + (right - left) // 2.
     • If nums[mid] == target:
       • Update start to mid
       • Move left = mid + 1 to find if there is any other occurence on the right side
     • If nums[mid] < target:
       • Move left = mid + 1.
     • Else:
       • Move right = mid - 1.
3. Return [start, end].

Code (Python):

def search_range(nums, target):
    def find_leftmost(nums, target):
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                index = mid
                right = mid - 1  # Continue searching on the left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return index

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

    left = find_leftmost(nums, target)
    right = find_rightmost(nums, target)
    return [left, right]

Time and Space Complexity:

• Time Complexity: O(log n), where n is the number of elements in the array, because we are using binary search twice.
• Space Complexity: O(1), as we use a constant amount of extra space.

Edge Cases:

• Empty Array: If the input array is empty, return [-1, -1].
• Target Not Found: If the target is not in the array, both binary searches will return -1, so the result will be [-1, -1].
• Single Element Array: If the array has only one element, check if that element is the target. If so, return [0, 0]; otherwise, return [-1, -1].
• Target at the Beginning/End: Ensure the binary search correctly identifies the first and last occurrences when the target appears at the start or end of the array.