Search For Range

Tags

Search For Range

Category

Searching

Difficulty

Hard

Problem Statement

Given a sorted array of integers and a target integer, find the range (starting and ending indices) of the target in the array. If the target is not found, return [-1, -1].

Intuition

Since the array is sorted, binary search can locate the target in O(log n). To find the range, we perform two modified binary searches: one biased to find the leftmost occurrence and another biased to find the rightmost occurrence. Each search narrows in on its respective boundary by continuing to search even after finding a match.

Approach

  1. Perform a binary search to find the leftmost index of the target:
    • When array[mid] == target, record mid and continue searching left (right = mid - 1).
  2. If the target is not found, return [-1, -1].
  3. Perform a binary search to find the rightmost index of the target:
    • When array[mid] == target, record mid and continue searching right (left = mid + 1).
  4. Return [leftIndex, rightIndex].

Pseudocode

function searchForRange(array, target):
    range = [-1, -1]
    range[0] = binarySearch(array, target, goLeft=true)
    range[1] = binarySearch(array, target, goLeft=false)
    return range

function binarySearch(array, target, goLeft):
    left = 0
    right = length(array) - 1
    result = -1

    while left <= right:
        mid = (left + right) / 2

        if array[mid] < target:
            left = mid + 1
        else if array[mid] > target:
            right = mid - 1
        else:
            result = mid
            if goLeft:
                right = mid - 1
            else:
                left = mid + 1

    return result

Time & Space Complexity

  • Time: O(log n) — two binary searches, each O(log n).
  • Space: O(1) — iterative binary search uses constant space.

Key Insights

  • The trick is not stopping at the first match. By continuing the search in one direction after finding the target, we converge on the boundary.
  • Both searches are independent and can conceptually run in parallel, though sequential execution is simpler.
  • This is more efficient than finding any occurrence and then linearly scanning for boundaries, which would degrade to O(n) if all elements are the target.

Edge Cases

  • Target not in the array: return [-1, -1].
  • Target appears exactly once: both indices are the same.
  • All elements equal the target: return [0, n-1].
  • Empty array: return [-1, -1].
  • Target is smaller than the minimum or larger than the maximum element.

Linked mentions