Editing Binary search (section)

=== Fractional cascading ===
{{Main|Fractional cascading}}
[[File:Fractional cascading.svg|thumb|upright=1.8|In [[fractional cascading]], each array has pointers to every second element of another array, so only one binary search has to be performed to search all the arrays.]]
Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays. Searching each array separately requires <math display="inline">O(k \log n)</math> time, where <math display="inline">k</math> is the number of arrays. Fractional cascading reduces this to <math display="inline">O(k + \log n)</math> by storing specific information in each array about each element and its position in the other arrays.<ref name="ChazelleLiu2001">{{cite conference|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|author-link1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|conference=33rd [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|pages=322–329|date=6 July 2001|doi=10.1145/380752.380818|url=https://dl.acm.org/citation.cfm?doid=380752.380818 |access-date=30 June 2018 |publisher=ACM|isbn=978-1-58113-349-3}}</ref><ref name="ChazelleLiu2004">{{cite journal|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|author-link1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|journal=Journal of Computer and System Sciences|date=1 March 2004 |volume=68|issue=2|pages=269–284 |language=en |issn=0022-0000|doi=10.1016/j.jcss.2003.07.003|citeseerx=10.1.1.298.7772|url=http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf |archive-date=2022-10-09 |url-status=live|access-date=30 June 2018}}</ref>

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.<ref name="ChazelleLiu2001" />