Equal Range Search

Equal range search finds the contiguous range of indices where a value $x$ appears in a sorted array. It returns a pair of indices:

$$ [l, r) $$

such that all elements equal to $x$ lie within this interval.

This operation combines lower bound and upper bound.

Problem

Given a sorted array $A$ of length $n$ and a value $x$, find indices $l$ and $r$ such that:

$$ A[i] = x \quad \text{for all } i \in [l, r) $$

If $x$ does not appear, return an empty range where $l = r$.

Key Idea

Compute:

• $l = \text{lower_bound}(x)$
• $r = \text{upper_bound}(x)$

Then:

$$ [l, r) $$

contains all occurrences of $x$.

Algorithm

equal_range(A, x):
    l = lower_bound(A, x)
    r = upper_bound(A, x)
    return (l, r)

Example

Let

$$ A = [1, 3, 3, 3, 5, 7] $$

and

$$ x = 3 $$

Then:

• lower bound = $1$
• upper bound = $4$

So the result is:

$$ [1, 4) $$

Interpretation

• Elements in $[l, r)$ are equal to $x$
• Elements before $l$ are less than $x$
• Elements from $r$ onward are greater than $x$

This forms a clean partition of the array.

Correctness

Lower bound ensures:

$$ A[l] \ge x $$

Upper bound ensures:

$$ A[r] > x $$

Together:

• all indices in $[l, r)$ satisfy $A[i] = x$
• no index outside the range contains $x$

Complexity

operation	time
lower bound	$O(\log n)$
upper bound	$O(\log n)$
total	$O(\log n)$

Space:

$$ O(1) $$

Use Cases

• Count occurrences:

$$ r - l $$

• Range queries in sorted arrays
• Deduplication boundaries
• Frequency counting without scanning

Implementation

def equal_range(a, x):
    def lower_bound(a, x):
        l, r = 0, len(a)
        while l < r:
            m = l + (r - l) // 2
            if a[m] < x:
                l = m + 1
            else:
                r = m
        return l

    def upper_bound(a, x):
        l, r = 0, len(a)
        while l < r:
            m = l + (r - l) // 2
            if a[m] <= x:
                l = m + 1
            else:
                r = m
        return l

    l = lower_bound(a, x)
    r = upper_bound(a, x)
    return (l, r)

func EqualRange(a []int, x int) (int, int) {
    lower := func(a []int, x int) int {
        l, r := 0, len(a)
        for l < r {
            m := l + (r-l)/2
            if a[m] < x {
                l = m + 1
            } else {
                r = m
            }
        }
        return l
    }

    upper := func(a []int, x int) int {
        l, r := 0, len(a)
        for l < r {
            m := l + (r-l)/2
            if a[m] <= x {
                l = m + 1
            } else {
                r = m
            }
        }
        return l
    }

    l := lower(a, x)
    r := upper(a, x)
    return l, r
}