Fractional Cascading: One Binary Search Through Many Lists

The problem: repeated searches across related lists

Consider a scenario common in computational geometry: a set of k line segments sliced by a family of vertical lines, where at each vertical line you need to know which of the segments crossing it are immediately above and below a query point. If each slice is stored as its own sorted array of y-coordinates, answering one query naively means running a separate binary search on every one of the k slices, giving O(k log n) time per query even though the slices are closely related to each other and their sorted orders barely change from one slice to the next. This pattern recurs constantly: layered range trees, planar point location structures, interval stabbing queries, and multilevel indexing schemes in databases all face the same shape of problem, where a single logical query needs an answer from every level of a hierarchy of sorted data. The wasted effort is that each binary search essentially rediscovers information the previous search already implied, since consecutive lists in these applications tend to be structurally similar, differing only by a few elements inserted, removed, or shifted between levels.

Building bridges: augmenting each list with samples from its neighbor

Fractional cascading's construction step processes the chain of lists from the last one backward to the first, augmenting each list with extra sampled elements drawn from the list that follows it. Concretely, every other element, roughly half, of the augmented version of list i+1 gets inserted into list i as a bridge element, merged into list i's sorted order and tagged with a pointer back to its original position in list i+1. This means the augmented list i is roughly the same asymptotic size as the original, since geometric series of halving sample sizes sum to a constant factor, but it now carries embedded signposts pointing forward into the next list's structure. After this preprocessing, every element in an augmented list carries a pointer to the nearest bridge element in the next list down the chain, so that once you have located your query's position in one augmented list, following its associated pointer lands you within a small, constant-sized neighborhood of the correct position in the next list, even without knowing anything else about that next list's specific contents.

Querying: one binary search, then constant-time hops

With the augmented structure built, answering a query for key x proceeds by first performing a single ordinary binary search for x in the augmented version of the first list, costing the usual O(log n) time. From there, at every subsequent level, rather than searching from scratch, the algorithm follows the bridge pointer associated with the nearest located element to jump into an approximate position in the next augmented list, then does a small constant amount of local scanning, typically comparing against just two or three neighboring elements, to pinpoint the exact correct position at that level. Because the sampling density guarantees that consecutive levels' bridge points are close together relative to the query's already-known neighborhood, this local correction never needs more than O(1) comparisons per level. The total cost across k levels becomes O(log n) for the first search plus O(k) for the constant-time hops through the remaining levels, a dramatic improvement over the naive O(k log n), especially as the number of levels k grows large relative to any single list's size.

Why this works: the catalog structure intuition

An intuitive way to understand fractional cascading is to imagine a chain of mail-order catalogs, where each catalog is a sorted list of items, and each catalog additionally contains a handful of representative entries sampled from the next catalog in the chain along with a page reference into that catalog. If you know a product's approximate position in catalog one, and catalog one happens to also list a sampled entry from catalog two right near that position along with a page number, you can flip almost directly to the right neighborhood in catalog two without rescanning it from the beginning. The mathematics behind why sampling every other element suffices, rather than needing to sample everything, hinges on the fact that gaps between consecutive samples in an augmented list are bounded, so no matter where the true answer falls between two adjacent samples, the true position in the un-augmented next-level list can be found by checking only a small fixed number of neighbors around the sample's known target position, never requiring a fresh search from an unknown starting point.

Applications beyond geometry

While fractional cascading was invented to speed up planar point location and related geometric algorithms, its core pattern, avoid repeating a search when you already know roughly where to look next, shows up throughout systems and algorithm design. Layered range trees for orthogonal range queries in two or more dimensions use fractional cascading between levels to answer multi-dimensional queries in time close to what a single dimension's binary search would cost. Iterative algorithms that repeatedly query a chain of versions of a changing sorted structure, such as certain persistent data structure implementations, benefit from cascading pointers between successive versions. Even outside of formal computer science curricula, the underlying idea appears informally in systems that maintain multiple sorted indexes over the same or closely related data and want to avoid redundant lookups, such as multi-resolution or multi-level indexing schemes in databases and search engines, wherever a query needs to be resolved consistently across a hierarchy of related sorted views of data that do not change drastically from one level to the next.

Frequently asked questions

Try it live

Everything above runs in your browser — open Fractional Cascading: One Binary Search Through Many Lists and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.