Fractional Cascading

Concepts: pyFractionalCascading, pyIndexTraversal

You have K sorted lists and a query value x. You want to find x's position in each of the K lists. Naive approach: binary search each list independently in O(K log N). Fractional cascading brings this down to O(K + log N) by doing the first binary search normally and then propagating that position information into subsequent lists, so each subsequent search starts from a known position and only scans a constant number of additional elements. The Core Idea Build augmented lists where every other element of each list is 'cascaded' into the list above it, along with a pointer back to its position in the original list. When you binary search the first augmented list, you find x's approximate position in all subsequent lists simultaneously. Each subsequent lookup becomes O(1) instead of O(log N