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
}