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

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

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

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

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
}