# Uniform Binary Search

# Uniform Binary Search

Uniform binary search is a variant of binary search that replaces midpoint computation with a sequence of precomputed offsets. It avoids repeated division and uses fixed step sizes that decrease over time.

This approach was designed for environments where division is expensive or unavailable.

## Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$
A[i] = x
$$

If no such index exists, return $-1$.

## Key Idea

Instead of computing

$$
m = \frac{l + r}{2}
$$

at each step, precompute a sequence of decreasing offsets:

$$
k_0, k_1, k_2, \dots
$$

Each step moves forward or backward by the current offset.

The offsets correspond to powers of two or a similar halving sequence.

## Algorithm

1. Start at a central position
2. Use a step size $k$
3. Compare $A[i]$ with $x$
4. Move left or right by $k$
5. Reduce $k$ and repeat

```id="ubs-1"
uniform_binary_search(A, x):
    n = length(A)

    # largest power of two <= n
    k = 1
    while k <= n:
        k = k * 2
    k = k // 2

    i = k - 1

    while k > 0:
        if i >= n:
            i = i - k
        else if A[i] == x:
            return i
        else if A[i] < x:
            i = i + k
        else:
            i = i - k

        k = k // 2

    return -1
```

## Example

Let

$$
A = [2, 4, 6, 8, 10, 12, 14, 16]
$$

and

$$
x = 10
$$

Offsets: $4, 2, 1$

Start at index $3$:

| step | k | i | A[i] | action     |
| ---- | - | - | ---- | ---------- |
| 1    | 4 | 3 | 8    | move right |
| 2    | 2 | 7 | 16   | move left  |
| 3    | 1 | 5 | 12   | move left  |
| 4    | 0 | 4 | 10   | found      |

Return index $4$.

## Correctness

The algorithm simulates binary search using fixed step sizes. At each stage, the step size halves, ensuring that the search interval shrinks similarly to standard binary search.

The sequence of movements converges to the correct position because each step reduces the maximum possible error by half.

## Complexity

| case      | time        |
| --------- | ----------- |
| all cases | $O(\log n)$ |

Space:

$$
O(1)
$$

## Comparison with Standard Binary Search

| feature              | standard        | uniform                        |
| -------------------- | --------------- | ------------------------------ |
| midpoint computation | division        | none                           |
| control flow         | dynamic         | fixed pattern                  |
| performance          | general purpose | useful in constrained hardware |

Uniform binary search trades flexibility for predictable computation.

## When to Use

* Environments without fast division
* Embedded systems
* Hardware level implementations
* Situations requiring predictable instruction patterns

## Notes

* Rarely used in modern software due to cheap arithmetic operations
* Conceptually useful for understanding search patterns
* Can be adapted to branchless implementations

## Implementation

```id="py-ubs"
def uniform_binary_search(a, x):
    n = len(a)

    k = 1
    while k <= n:
        k *= 2
    k //= 2

    i = k - 1

    while k > 0:
        if i >= n:
            i -= k
        elif a[i] == x:
            return i
        elif a[i] < x:
            i += k
        else:
            i -= k

        k //= 2

    return -1
```

```id="go-ubs"
func UniformBinarySearch(a []int, x int) int {
    n := len(a)

    k := 1
    for k <= n {
        k *= 2
    }
    k /= 2

    i := k - 1

    for k > 0 {
        if i >= n {
            i -= k
        } else if a[i] == x {
            return i
        } else if a[i] < x {
            i += k
        } else {
            i -= k
        }
        k /= 2
    }

    return -1
}
```