Say you have k sorted catalogs — unrelated arrays, not levels of one tree — and a
query value v, and you want lower_bound(v) (the smallest element
≥ v) in every catalog, not just one. The obvious approach is k
independent binary searches, O(k log n) total. Fractional cascading gets the same
answer in O(log n + k): binary search for real exactly once, in a single augmented
list built on top of the first catalog, then follow one pointer per remaining catalog and check at
most two neighboring entries — O(1) a level, not O(log n) a level. The
trick is what goes into that augmented list: each catalog's own elements, plus every other element
promoted up from the next catalog's augmented list, so a position found in one level's list is
never more than a couple of slots from the right answer one level down.
Three catalogs: L0 (4 values), L1 (7 values), and L2 (8 values), all drawn from disjoint value ranges so every comparison below has one unambiguous answer. Enter a query value and press Load Query to build the step sequence: a real binary search in A0, the augmented top list, followed by a down-pointer jump plus an O(1) correction check into A1 and then A2. In the augmented row, solid cells are native to that level's own catalog; faded cells are promoted markers copied up from a deeper level, present only to steer the search — never themselves an answer for this level.
Building the augmented lists, bottom-up. A[k-1] is just
L[k-1] itself — nothing to promote from below. For each shallower level
i, take every other element of A[i+1] (positions 0, 2, 4, ...)
and merge those promoted values into L[i]'s own native values,
keeping the result sorted. Sampling from A[i+1] — the already-augmented list — rather
than the raw L[i+1] is what lets the bridges compose across every level at once:
A[i+1]'s own promoted entries already carry pointers further down, so a marker
promoted into A[i] inherits that whole chain for free.
Down-pointers, computed with one backward pass. Every entry of
A[i] gets a down index into A[i+1]: for a promoted entry
it's exactly where that value sits in A[i+1]; for a native entry it's the nearest
promoted entry's target at or after it, found by walking the merged list back-to-front and
carrying the most recently seen promoted target along. A second table,
nativeAtOrAfter, does the same backward carry for "nearest position that's actually
native to L[i]" — needed because the position a query lands on inside
A[i] is very often a promoted ghost, not a real member of L[i], and the
value actually reported for this level has to be the nearest real one.
The O(1) correction. Binary search finds p = lower_bound(v) in
A[0] for real, O(log n0). From there, q = A[0][p].down
lands in A[1] — and the true lower_bound(v) in A[1] is
always at position q or q - 1, never farther, so checking those two
entries (in that order, smaller index first) always finds it. Verified two ways before writing any
of this: exhaustively, all 5,796 ways to split 8 distinct values across 3 non-empty sorted
catalogs, every query value from one below the minimum to one above the maximum — 63,756
checks, 0 mismatches — and 300,000 randomized checks (2-6 catalogs, up to 14 elements
each, values up to 800) against independent per-catalog binary search as the reference — again
0 mismatches, with the down-pointer target itself already correct (no correction
needed at all) in 95,287 of those 300,000 cases and needing exactly the one-step-back check in the
rest. No case in either sweep ever needed to look further than that.
Worked example, v = 50. A0 is
[5,10,20,40,45,70,75,95,100,110] (native: 10,40,70,100). Binary search lands on
position 5, value 70 — L0's answer. Its down-pointer is 6, into
A1 = [5,15,20,35,45,55,75,80,95,105,110] (native: 5,20,35,55,80,95,110); checking
position 6 first (value 75, too big) then position 5 (value 55, ≥ 50) lands the correction on
position 5 — L1's answer. That entry's down-pointer is 4, into
A2 = [15,30,45,60,75,90,105,120] (fully native, no level below it); position 4 is 75
(too big), position 3 is 60 (≥ 50) — L2's answer. Total: 5 comparisons
(4 to binary search A0's 10 entries, plus one hit on the very first correction check
each level) versus 8 for three independent binary searches
(⌈log₂4⌉ + ⌈log₂7⌉ + ⌈log₂8⌉ = 2 + 3 + 3) on the same three catalogs.
class FractionalCascade {
constructor(lists) {
this.lists = lists;
const k = lists.length;
const A = new Array(k);
A[k - 1] = lists[k - 1].map((v, idx) => ({ value: v, native: true, nativeIndex: idx, down: null }));
for (let i = k - 2; i >= 0; i--) {
const next = A[i + 1];
const sample = [];
for (let j = 0; j < next.length; j += 2) sample.push({ value: next[j].value, downIdx: j });
const merged = [];
let a = 0, b = 0;
const native = lists[i];
while (a < native.length || b < sample.length) {
if (b >= sample.length || (a < native.length && native[a] < sample[b].value)) {
merged.push({ value: native[a], native: true, nativeIndex: a, down: null });
a++;
} else {
merged.push({ value: sample[b].value, native: false, nativeIndex: -1, down: sample[b].downIdx });
b++;
}
}
let nextDown = next.length; // sentinel: no promoted target at or after here
for (let m = merged.length - 1; m >= 0; m--) {
if (!merged[m].native) nextDown = merged[m].down;
else merged[m].down = nextDown;
}
A[i] = merged;
}
this.A = A;
// nativeAtOrAfter[i][p] = index into lists[i] of the nearest native entry at/after position p
this.nativeAtOrAfter = A.map((level) => {
const arr = new Array(level.length + 1);
arr[level.length] = null;
for (let j = level.length - 1; j >= 0; j--) {
arr[j] = level[j].native ? level[j].nativeIndex : arr[j + 1];
}
return arr;
});
}
static lowerBoundOf(level, v) {
let lo = 0, hi = level.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (level[mid].value >= v) hi = mid; else lo = mid + 1;
}
return lo;
}
// results[i] = smallest value in lists[i] that is >= v, or null
lowerBound(v) {
const { A, nativeAtOrAfter, lists } = this;
const k = A.length;
const results = [];
let p = FractionalCascade.lowerBoundOf(A[0], v); // the only real binary search: O(log n0)
for (let i = 0; i < k; i++) {
const natIdx = nativeAtOrAfter[i][p];
results.push(natIdx === null ? null : lists[i][natIdx]);
if (i < k - 1) {
const q = p === A[i].length ? A[i + 1].length : A[i][p].down;
let best = A[i + 1].length;
for (let x = Math.max(0, q - 1); x <= q && x < A[i + 1].length; x++) {
if (A[i + 1][x].value >= v) { best = x; break; }
}
p = best; // O(1): at most two positions checked
}
}
return results;
}
}Re-verified this exact class against the same two harnesses (exhaustive and randomized) after writing it: 300,000 randomized checks, 0 mismatches, and the demo's own worked numbers above come directly from running it, not a hand-traced approximation.
The correction must check backward from the down-pointer, never forward. It's
tempting to check q and q + 1 instead of q - 1 and
q — "the pointer already lands near the answer, so look from there onward." That
version is wrong far more often than right: rerunning the same 300,000-case harness with the
window flipped to [q, q + 1] failed 204,113 of 300,000 checks (68%).
The reason is what down actually means: it points to the smallest promoted
element ≥ v's source value, and a smaller value that's native only to
A[i+1] — never sampled up into A[i] at all — can sit just before that
promoted marker and still qualify as the true lower_bound(v). A concrete counter
-example the harness found: five catalogs, query v = 228, expected
[421, 245, 376, 255, 242]; the forward-window version returned
[421, 400, 376, 359, 516] — three of five levels wrong, each one overshooting to a
larger value that happened to be promoted, having skipped past a smaller native one sitting just
behind it.
A position in A[i] is not automatically the answer for
L[i]. An early version of the code above set
nativeAtOrAfter[j] = j — the raw position within A[i] — instead of that
entry's actual index within L[i]. It looked plausible: every lookup still returned
some in-bounds value from the right catalog, no crash, no obviously wrong shape. It silently broke
the moment a query landed on a promoted (non-native) position, which is most of the time once
L[i] is smaller than the samples merged into it — 86,275 of 100,000
randomized checks failed against independent per-catalog binary search before the fix,
0 after switching to storing each native entry's real index into its own catalog
and carrying that backward the same way down is carried.
Time: building all k augmented lists costs
O(n) total, where n is the combined size of every catalog — each level's
merge is linear in its own size, and the geometric falloff of "every other element" promoted
upward keeps |A[i]| within a constant factor of |L[i]| + |A[i+1]|, so the
levels don't blow up in total size. A query costs O(log n0) for the one real binary
search plus O(1) per remaining catalog, O(log n0 + k) total, against
O(k log n) for k independent binary searches over catalogs of comparable
size. Space: O(n) for the same reason the build is linear — every
augmented list holds its own catalog plus a shrinking sample from the one below it.
The gap between the two costs is modest at the three-catalog, single-digit-to-teens scale this
page's demo uses (5 comparisons versus 8 above) and widens with both k and catalog
size, measured directly by instrumenting both approaches on randomized catalogs of growing size:
1.34× fewer comparisons at 3 catalogs of 8 elements each, 1.89×
at 5 catalogs of 16, 2.46× at 8 catalogs of 32, and 2.96× at 10
catalogs of 64 (200 randomized queries averaged per size). This site's guide, Choosing a Range Query Structure, sets
this entry aside the same way it already sets aside Binary Heap, Mo's Algorithm, Van Emde Boas Tree, and Wavelet Tree — a fifth "different question" case.
The guide's six compared entries all maintain one running answer over a changing array. Fractional
cascading instead speeds up the same query repeated across several unrelated, unchanging
catalogs — closer in spirit to the layered search behind 2D
range trees (where the "catalogs" are a segment tree's per-node associated lists) than to any
single structure's own query.