# Eytzinger Layout Search

# Eytzinger Layout Search

Eytzinger layout search reorganizes a sorted array into a breadth first tree layout, also known as heap order. The goal is to improve cache locality and make memory access patterns more predictable.

Instead of storing data in sorted order, the array is rearranged so that binary search follows a sequential memory pattern. This reduces cache misses and improves throughput on modern CPUs.

## Problem

Given a sorted array $A$ and a target $x$, find an index $i$ such that

$$
A[i] = x
$$

The data is stored in Eytzinger layout rather than sorted order.

## Layout

In Eytzinger layout, the array represents a complete binary tree:

* root at index $1$
* left child at $2i$
* right child at $2i + 1$

The values are placed so that an in order traversal yields the sorted sequence.

Example:

Sorted array:

$$
[3, 6, 9, 12, 15, 18, 21]
$$

Eytzinger layout:

| index | value |
| ----- | ----- |
| 1     | 12    |
| 2     | 6     |
| 3     | 18    |
| 4     | 3     |
| 5     | 9     |
| 6     | 15    |
| 7     | 21    |

## Idea

Search proceeds like traversing a binary search tree, but the nodes are stored in a flat array. Each step moves to either the left or right child.

The key benefit is that memory access becomes more predictable, often prefetch friendly.

## Algorithm

```id="ey01"
eytzinger_search(A, x):
    i = 1
    n = length(A) - 1   # assume 1-based array

    while i <= n:
        if A[i] == x:
            return i

        if x < A[i]:
            i = 2 * i
        else:
            i = 2 * i + 1

    return -1
```

To support lower bound queries, track the last position where the value was greater than or equal to $x$.

## Example

Using the layout above, search for:

$$
x = 15
$$

Traversal:

| step | index | value | action   |
| ---- | ----- | ----- | -------- |
| 1    | 1     | 12    | go right |
| 2    | 3     | 18    | go left  |
| 3    | 6     | 15    | found    |

## Correctness

The layout preserves the binary search tree invariant:

* left subtree contains smaller values
* right subtree contains larger values

Thus each comparison eliminates half of the remaining candidates, exactly like binary search. The difference lies only in memory arrangement, not logical behavior.

## Complexity

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

Space:

$$
O(n)
$$

The array is a permutation of the original data.

## When to Use

Use Eytzinger layout when:

* data is static
* search dominates workload
* cache performance is critical
* branch prediction and memory access patterns matter

It is widely used in high performance search systems and database indexes.

## Implementation

```id="ey02"
def build_eytzinger(sorted_array):
    n = len(sorted_array)
    e = [None] * (n + 1)
    i = 0

    def dfs(k):
        nonlocal i
        if k <= n:
            dfs(2 * k)
            e[k] = sorted_array[i]
            i += 1
            dfs(2 * k + 1)

    dfs(1)
    return e

def eytzinger_search(e, x):
    i = 1
    n = len(e) - 1

    while i <= n:
        if e[i] == x:
            return i
        if x < e[i]:
            i = 2 * i
        else:
            i = 2 * i + 1

    return -1
```

```id="ey03"
func EytzingerSearch(e []int, x int) int {
    i := 1
    n := len(e) - 1

    for i <= n {
        if e[i] == x {
            return i
        }
        if x < e[i] {
            i = 2 * i
        } else {
            i = 2*i + 1
        }
    }

    return -1
}
```