Fractional Cascading Search

Fractional cascading search speeds up repeated searches across several related sorted lists. Instead of running a separate binary search in each list, it performs one full binary search, then uses precomputed links to continue the search in nearby positions of the remaining lists.

It is useful when the same query value must be located in many sorted catalogs.

Problem

Given $k$ sorted lists:

L_1, L_2, \dots, L_k

and a query value $x$ , find the lower bound position of $x$ in each list.

A direct method runs binary search in each list:

O(k \log n)

Fractional cascading reduces this to:

O(\log n + k)

after preprocessing.

Key Idea

Build augmented lists. Each augmented list contains:

all elements from its original list
a fraction of elements copied from the next augmented list
pointers to corresponding lower bound positions in both lists

After one binary search in the first augmented list, each later result is found by following links and doing only constant additional work.

Algorithm

Preprocessing:

build_fractional_cascading(L):
    C[k] = L[k]

    for i from k - 1 down to 1:
        sampled = every_second_element(C[i + 1])
        C[i] = merge(L[i], sampled)

        for each element y in C[i]:
            y.local_index = lower_bound(L[i], y)
            y.next_index = lower_bound(C[i + 1], y)

    return C

Query:

fractional_cascading_search(C, x):
    p = lower_bound(C[1], x)

    for i from 1 to k:
        answer[i] = C[i][p].local_index

        if i < k:
            p = C[i][p].next_index
            adjust p by checking nearby elements

    return answer

Example

Suppose one query value $x$ must be searched in four sorted lists.

Without fractional cascading:

list	search cost
$L_1$	$O(\log n)$
$L_2$	$O(\log n)$
$L_3$	$O(\log n)$
$L_4$	$O(\log n)$

Total:

O(4 \log n)

With fractional cascading:

step	cost
first binary search	$O(\log n)$
follow links through lists	$O(4)$

Total:

O(\log n + 4)

Correctness

The augmented lists preserve the sorted order of each original list. Each element stores enough information to translate a search position in one augmented list into a nearby search position in the next one.

Because sampled elements from the next list are copied upward, the true lower bound in the next list can differ from the linked position by only a constant number of steps. The local adjustment recovers the exact lower bound.

Thus the first binary search identifies a correct starting position, and each link transfer preserves correctness for the next list.

Complexity

Let $N$ be the total number of stored original elements and $k$ be the number of lists.

phase	time	space
preprocessing	$O(N)$	$O(N)$
query	$O(\log n + k)$	$O(k)$

The query time assumes the lists are related through the fractional cascading structure and each transfer requires constant adjustment.

Comparison

method	query time	preprocessing
independent binary searches	$O(k \log n)$	none
fractional cascading	$O(\log n + k)$	$O(N)$

Fractional cascading trades preprocessing and extra storage for faster repeated queries.

When to Use

Use fractional cascading when:

many sorted lists are searched by the same query value
queries are repeated many times
preprocessing is acceptable
the lists belong to a fixed geometric or graph structure

Common applications include range searching, computational geometry, segment trees with sorted catalogs, and planar subdivision queries.

Notes

The structure is more complex than ordinary binary search.
It is usually unnecessary for one-off queries.
It is most valuable when the same search value propagates through many related catalogs.
Segment trees with sorted vectors can use this idea to reduce query-time logarithmic factors.

Implementation Sketch

from bisect import bisect_left

class FCEntry:
    def __init__(self, value, local_index, next_index):
        self.value = value
        self.local_index = local_index
        self.next_index = next_index

def lower_bounds_independent(lists, x):
    return [bisect_left(lst, x) for lst in lists]

A full production implementation must build augmented catalogs and stable cross-links between them. The independent version above shows the baseline that fractional cascading improves.