Home▸Algorithms & AI▸Fractional Cascading: One Binary Search Through Many Lists

🔗 Fractional Cascading: One Binary Search Through Many Lists

Discover how fractional cascading searches the same key across a chain of sorted arrays by embedding bridging pointers, cutting repeated binary searches down to a single one followed by constant-time steps per level.

Algorithms & AI3DModerate60 FPS

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.

🔬 What It Demonstrates

🎮 How to Use

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.

💡 Did You Know?

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.

⚙ Under the hood

fractional cascadingalgorithmsbinary searchdata structurescomputational geometrysearch optimizationsorted arraysamortized analysis

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install