# Branchless Binary Search

# Branchless Binary Search

Branchless binary search is a binary search variant designed to reduce branch mispredictions. A normal binary search repeatedly branches on whether the middle value is less than the target. On modern CPUs, this branch can be hard to predict because the search direction depends on the data.

A branchless version keeps the same comparison logic but updates the search position using conditional moves, masks, or arithmetic expressions. The algorithm remains logarithmic, but it may run faster on large arrays where branch misprediction dominates.

## Problem

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

$$
A[i] \ge x
$$

This is the lower bound problem. Exact membership search can then check whether $A[i] = x$.

## Idea

Instead of writing:

```id="bbs01"
if A[mid] < x:
    left = mid + 1
else:
    right = mid
```

use an update form that the compiler can lower to conditional move instructions.

The search maintains a base position and a step size. At each step, it probes a candidate position. If the candidate value is still less than the target, the base moves forward. Otherwise, the base stays unchanged.

## Algorithm

```id="bbs02"
branchless_lower_bound(A, x):
    n = length(A)
    base = -1
    step = highest_power_of_two_less_than_or_equal_to(n)

    while step > 0:
        next = base + step

        if next < n and A[next] < x:
            base = next

        step = step // 2

    return base + 1
```

The important implementation detail is that the `if` can be compiled as a conditional move rather than a branch.

## Example

Let

$$
A = [3, 6, 9, 12, 15, 18, 21, 24]
$$

and

$$
x = 16
$$

The lower bound is index $5$, because:

$$
A[5] = 18
$$

Trace:

| step | probe index | value | value < x | base after |
| ---- | ----------: | ----: | --------- | ---------: |
| 4    |           3 |    12 | yes       |          3 |
| 2    |           5 |    18 | no        |          3 |
| 1    |           4 |    15 | yes       |          4 |

Return:

$$
base + 1 = 5
$$

## Correctness

The variable `base` always stores the largest known index whose value is less than $x$. Initially, no such index is known, so `base = -1`.

Each probe tests whether a farther candidate also satisfies $A[next] < x$. If it does, the candidate becomes the new largest known valid index. If it does not, the base stays unchanged. The step size then halves, so the algorithm refines the answer bit by bit.

When the loop ends, no larger index with value less than $x$ remains untested. Therefore `base + 1` is the first index whose value is greater than or equal to $x$.

## Complexity

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

Space:

$$
O(1)
$$

The asymptotic cost matches ordinary binary search. The difference is practical: branchless search trades control flow for arithmetic or conditional moves.

## When to Use

Use branchless binary search when:

* the array is sorted
* searches are frequent
* the array is large enough for branch costs to matter
* query keys are unpredictable
* performance profiling shows branch misprediction overhead

For small arrays, ordinary binary search is often simpler and just as fast.

## Implementation

```id="bbs03"
def lower_bound(a, x):
    base = -1
    step = 1

    while step * 2 <= len(a):
        step *= 2

    while step > 0:
        nxt = base + step
        if nxt < len(a) and a[nxt] < x:
            base = nxt
        step //= 2

    return base + 1

def branchless_binary_search(a, x):
    i = lower_bound(a, x)
    if i < len(a) and a[i] == x:
        return i
    return -1
```

```id="bbs04"
func BranchlessLowerBound(a []int, x int) int {
    n := len(a)
    base := -1
    step := 1

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

    for step > 0 {
        next := base + step
        if next < n && a[next] < x {
            base = next
        }
        step /= 2
    }

    return base + 1
}

func BranchlessBinarySearch(a []int, x int) int {
    i := BranchlessLowerBound(a, x)
    if i < len(a) && a[i] == x {
        return i
    }
    return -1
}
```