# Powers of Two Search

# 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

```id="pow2-search-1"
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.

```id="pow2-first-true"
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

```id="py-pow2-search"
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
```

```id="go-pow2-search"
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
}
```