Powers of Two Search

Powers of two search finds a boundary in a monotone predicate by building the answer from large jumps to small jumps. It is a binary search variant written as controlled forward movement.

Instead of maintaining an interval, the algorithm keeps a current position and tries jumps of size:

$$ 2^k, 2^{k-1}, \dots, 2^1, 2^0 $$

This style is common in Fenwick trees, binary lifting, implicit arrays, and search over answer spaces.

Problem

Given a monotone predicate $P(i)$ over indices $0$ to $n - 1$, find the largest index $i$ such that:

$$ P(i) = true $$

Assume the predicate has the shape:

$$ true, true, true, false, false, false $$

If no index satisfies the predicate, return $-1$.

Key Idea

Start before the array at position $-1$. Try to jump forward by the largest power of two that may fit.

If the new position still satisfies $P$, accept the jump. Otherwise, reject it and try a smaller jump.

By the end, no positive jump can be added while preserving the predicate.

Algorithm

powers_of_two_search(n, P):
    pos = -1

    step = 1
    while step < n:
        step = step * 2

    while step > 0:
        next = pos + step
        if next < n and P(next):
            pos = next
        step = step // 2

    return pos

Example

Suppose:

index	0	1	2	3	4	5	6
P(i)	true	true	true	true	false	false	false

The largest true index is $3$.

The algorithm tries large jumps first, accepts only jumps that remain true, and ends at index $3$.

Relation to Binary Search

Standard binary search keeps an interval. Powers of two search keeps a position and a decreasing jump size.

Both rely on the same monotonicity condition and both take logarithmic time.

method	state	decision
binary search	interval $[l, r)$	keep left or right half
powers of two search	current position plus jump	accept or reject jump

Correctness

The algorithm maintains this invariant:

• pos is either $-1$ or an index satisfying $P(pos)$.
• No accepted jump ever crosses into a known false region.

When a candidate next = pos + step satisfies $P$, accepting the jump keeps pos valid and moves it closer to the largest true index.

When the candidate is out of bounds or false, monotonicity implies that this jump is too large from the current position, so the algorithm safely rejects it and tries smaller jumps.

After all powers of two have been tried, no remaining positive jump can be accepted. Therefore pos is the largest true index.

Complexity

cost	value
predicate evaluations	$O(\log n)$
time	$O(\log n \cdot T_P)$
space	$O(1)$

Here $T_P$ is the cost of evaluating $P$.

Common Uses

• Fenwick tree lower bound
• Binary lifting on trees
• Search over prefix sums
• Largest feasible answer
• Finding the last valid position in an implicit structure

Minimum True Variant

To find the first true index for a predicate shaped as:

$$ false, false, false, true, true, true $$

search for the last false index, then add one.

first_true_by_powers_of_two(n, P):
    last_false = powers_of_two_search(n, lambda i: not P(i))
    return last_false + 1

If all values are false, this returns $n$.

Implementation

def powers_of_two_search(n, pred):
    pos = -1

    step = 1
    while step < n:
        step *= 2

    while step > 0:
        nxt = pos + step
        if nxt < n and pred(nxt):
            pos = nxt
        step //= 2

    return pos

func PowersOfTwoSearch(n int, pred func(int) bool) int {
    pos := -1

    step := 1
    for step < n {
        step *= 2
    }

    for step > 0 {
        next := pos + step
        if next < n && pred(next) {
            pos = next
        }
        step /= 2
    }

    return pos
}