Meta Binary Search

Meta binary search (also called one-sided binary search) finds a value in a sorted array without ever computing a midpoint or dividing anything. Instead of shrinking a [lo, hi] window, it assembles the answer index one bit at a time, from the highest bit down to the lowest. It lands on the exact same position a classic binary search would — it just builds the index in binary rather than bisecting a range.

Intuition

A classic binary search keeps two moving walls, lo and hi, and computes mid = (lo + hi) / 2 every step. Meta binary search throws the walls away and asks a different question: what are the binary digits of the answer?

Any index in an array of length n can be written in bit_length(n) bits. So the answer is some bit pattern like 101. Meta binary search decides those bits greedily from the most significant down. At each bit it asks: "if I switch this bit on, does the cell I land on still satisfy a[pos] <= target?" If yes, switching it on only moves us closer to (or onto) the answer, so we commit it. If no, that bit overshoots, so we leave it off. Because the array is sorted, this greedy choice is always safe — and after every bit has been decided, pos is the last index whose value does not exceed the target.

This is why it is called one-sided: pos only ever moves forward (it never backtracks left), and it is division-free — the only arithmetic is pos + (1 << i), a shift and an add. That makes it attractive on hardware where division is expensive, and it generalizes neatly to searching implicit or huge ranges where you would rather not materialize lo and hi.

Walk through it

Step through the animation on the right. The row is the sorted array a; the pointer pos marks the index being assembled, and the readout up top shows the binary index taking shape and the bit currently under test.

We start with pos = 0 and lg = 4 because n = 8 is 1000 in binary. The loop sweeps bits 4, 3, 2, 1, 0. Bit 4 would jump to index 16 and bit 3 to index 8 — both past the end of an 8-element array, so they are cleared immediately. Bit 2 proposes new = 4; since a[4] = 9 <= 12, the bit stays and pos snaps to 4. Bit 1 proposes new = 6, but a[6] = 15 > 12, so it is dropped and pos stays 4. Bit 0 proposes new = 5; since a[5] = 12 <= 12, the bit stays and pos becomes 5. The assembled index is 101. Finally we check a[5] = 12 == 12 — a match — so the target lives at index 5.

The code, line by line

def meta_search(a, x):
    n = len(a)
    lg = n.bit_length()
    pos = 0
    for i in range(lg, -1, -1):
        new = pos + (1 << i)
        if new < n and a[new] <= x:
            pos = new
    return pos if a[pos] == x else -1

• lg = n.bit_length() is how many bits any valid index can need; for n = 8 that is 4, so the loop tries bits 4 down to 0.
• pos = 0 is the index we build up. It starts at zero and only ever grows — that is the one-sided part.
• Line 5 sweeps the bits from most significant to least, the reverse of how binary search narrows a range.
• Line 6, new = pos + (1 << i), tentatively turns bit i on. 1 << i is the bit value; there is no division anywhere.
• Line 7 is the guard. new < n keeps the index in bounds, and a[new] <= x is the sortedness test: if the candidate value does not exceed the target, the answer is at new or further right.
• Line 8 commits the bit by advancing pos = new. If the guard failed, we skip this and the bit stays 0.
• Line 9 makes the final decision. After the loop, pos is the last index with a[pos] <= x; it equals x exactly when x is present.

Complexity

The loop runs once per bit of the index, and an index needs about log2(n) bits, so the running time is O(log n) — identical to ordinary binary search. The work per step is a shift, an add, and one comparison, with no division and no extra memory.

When to use / pitfalls

Practice