Search for a Range

Question (LC.34)

Given a sorted array of integers, find the starting and ending position of a given target value.

Example

Input: [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Ask edge cases: if target doesn't exist in the array, return [-1, -1].

Brute Force

Linear scan. If find the target element, then extend the end index.

def searchRange(self, nums: List[int], target: int) -> List[int]:

    n = len(nums)
    
    if n == 0:
        return [-1, -1]
    
    start_index = -1 
    end_index = -1 
    found = False
    
    for i in range(n):
        if nums[i] == target:
            if not found:
                found = True
                start_index = i
                end_index = i
            else:
                end_index = i  
    
    return [start_index, end_index]
    

This solution's performance is surprisingly good on LC.

Runtime	Memory Usage
88 ms, faster than 32.93%	15.4 MB, less than 28.87%

Analysis

Given a sorted array and we want to find a target element, that's the job of binary search. On top of that, we want to do better than linear time.

Initial thought: find first or last index then for loop to find the range. runtime will be O(log(n) + range).

On a second thought, we can just do two binary searches. 1. find the first pos 2. find the last pos

Code

def searchRange(self, nums: List[int], target: int) -> List[int]:
    """    
    I: [5, 7, 7, 8, 8, 10], 8 
    
    S: [A, A, A, B, B, C, C, C]
    
    We need a binary search to find A -> B 
    
    another binary search to find B -> C 
    
    Walkthrough 
    
    I: [5, 7, 7, 8, 8, 10], 8 
        s     m         e
              s  m      e
              s. e
                 start_index = 3
    
        s     m         e 
              s  m      e
                 s  m   e
                    s.  e
                    end_index = 4 
        
    O: [3, 4]
    
    edge cases 
    
    1. [] 
    
    2. [-1, 0], -1 
    
    3. [1, 1, 1, 1], 1
    
    """
    
    n = len(nums)
    
    if n == 0:
        return [-1, -1]
    
    start_index = self.searchAB(nums, target, 0, n-1)
    
    if start_index == -1:
        return [-1, -1]
    
    end_index = self.searchBC(nums, target, 0, n-1)
    
    return [start_index, end_index]
    
    
def searchAB(self, nums: List[int], target: int, start: int, end: int) -> int:
    
    # base case (2 elements) 
    length = end - start + 1
    if length <= 2:
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1
    
    # dividing 
    
    middle = (start + end) // 2
    
    # discard left section, search right section
    if nums[middle] < target:
        return self.searchAB(nums, target, middle, end)
        
    elif nums[middle] == target:   
        # discard right section because we are looking for AB
        return self.searchAB(nums, target, start, middle)
        
    else: # nums[middle] > target
        # discard right section, search left section
        return self.searchAB(nums, target, start, middle)
    
def searchBC(self, nums: List[int], target: int, start: int, end: int) -> int:
    # base case (2 elements)
    length = end - start + 1
    if length <= 2:
        # if they are all the same, have to return the last one 
        if nums[end] == target:
            return end
        if nums[start] == target:
            return start
        return -1
    
    # dividing 
    middle = (start + end) // 2
    
    # discard left section, search right section
    if nums[middle] < target:
        return self.searchBC(nums, target, middle, end)
        
    elif nums[middle] == target:   
        # we want to discard left section because we are looking for BC
        return self.searchBC(nums, target, middle, end)
        
    else: # nums[middle] > target
        # discard right section, search left section
        return self.searchBC(nums, target, start, middle)

Time Complexity

Runtime	Memory Usage
80 ms, faster than 84.79%	15.5 MB, less than 28.87%

Now the time complexity is only $\log{n}$. The space complexity is also $\log{n}$because this implementation is recursive rather than in place two pointers. I don't think logarithmic space usage is that big of a deal.