The simulation builds a chain of sorted arrays with fractional cascading bridge pointers layered on top, then runs a query side by side against a naive per-list binary search to visually compare the number of comparisons each approach needs.
Set the number of lists and their sizes, click build to construct the augmented structure with visible bridge pointers, then enter a query key to watch the single initial binary search followed by constant-time hops down the chain.
Inputs for number of lists and list sizes, a build button, a query key field, and a naive-versus-cascaded comparison counter.
Fractional cascading gets its name because each level samples a fraction, specifically about half, of the elements from the level below, and this fraction cascades down the whole chain while still keeping every augmented list only a constant factor larger than its original size.
The simulation builds a chain of sorted arrays with fractional cascading bridge pointers layered on top, then runs a query side by side against a naive per-list binary search to visually compare the number of comparisons each approach needs.
The simulation builds a chain of sorted arrays with fractional cascading bridge pointers layered on top, then runs a query side by side against a naive per-list binary search to visually compare the number of comparisons each approach needs.
Set the number of lists and their sizes, click build to construct the augmented structure with visible bridge pointers, then enter a query key to watch the single initial binary search followed by constant-time hops down the chain.
Fractional cascading gets its name because each level samples a fraction, specifically about half, of the elements from the level below, and this fraction cascades down the whole chain while still keeping every augmented list only a constant factor larger than its original size.