# Equal Range Search

# 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

```id="eqr8p1"
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

```id="w9p3x2"
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)
```

```id="n2k7d5"
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
}
```