information:classification, structural:scholar_edition
Fractional cascading

Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays. Searching each array separately requires O (k log n) {\textstyle O(k\log n)} time, where k {\textstyle k} is the number of arrays. Fractional cascading reduces this to O (k + log n) {\textstyle O(k+\log n)} by storing specific information in each array about each element and its position in the other arrays.

Fractional cascading was originally developed to efficiently solve various computational geometry problems. Fractional cascading has been applied elsewhere, such as in data mining and Internet Protocol routing.