Editing Binary search (section)

== Variations ==

=== Uniform binary search ===
{{Main|Uniform binary search}}
[[File:Uniform binary search.svg|thumb|upright=1.0|[[Uniform binary search]] stores the difference between the current and the two next possible middle elements instead of specific bounds.]]
Uniform binary search stores, instead of the lower and upper bounds, the difference in the index of the middle element from the current iteration to the next iteration. A [[lookup table]] containing the differences is computed beforehand. For example, if the array to be searched is {{math|[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}}, the middle element (<math>m</math>) would be {{math|6}}. In this case, the middle element of the left subarray ({{math|[1, 2, 3, 4, 5]}}) is {{math|3}} and the middle element of the right subarray ({{math|[7, 8, 9, 10, 11]}}) is {{math|9}}. Uniform binary search would store the value of {{math|3}} as both indices differ from {{math|6}} by this same amount.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "An important variation"}} To reduce the search space, the algorithm either adds or subtracts this change from the index of the middle element. Uniform binary search may be faster on systems where it is inefficient to calculate the midpoint, such as on [[decimal computer]]s.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm U"}}

=== Exponential search{{anchor|One-sided search}} ===
{{Main|Exponential search}}
[[File:Exponential search.svg|thumb|upright=1.5|Visualization of [[exponential search]]ing finding the upper bound for the subsequent binary search]]
Exponential search extends binary search to unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary search. A search takes <math display="inline">\lfloor \log_2 x + 1\rfloor</math> iterations before binary search is started and at most <math display="inline">\lfloor \log_2 x \rfloor</math> iterations of the binary search, where <math display="inline">x</math> is the position of the target value. Exponential search works on bounded lists, but becomes an improvement over binary search only if the target value lies near the beginning of the array.{{sfn|Moffat|Turpin|2002|p=33}}

=== Interpolation search ===
{{Main|Interpolation search}}
[[File:Interpolation search.svg|thumb|upright=1.5|Visualization of [[interpolation search]] using linear interpolation. In this case, no searching is needed because the estimate of the target's location within the array is correct. Other implementations may specify another function for estimating the target's location.]]
Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

A common interpolation function is [[linear interpolation]]. If <math>A</math> is the array, <math>L, R</math> are the lower and upper bounds respectively, and <math>T</math> is the target, then the target is estimated to be about <math>(T - A_L) / (A_R - A_L)</math> of the way between <math>L</math> and <math>R</math>. When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes <math display="inline">O(\log \log n)</math> comparisons.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 22"}}<ref>{{cite journal|last1=Perl|first1=Yehoshua|last2=Itai|first2=Alon|last3=Avni|first3=Haim|s2cid=11089655|title=Interpolation search—a log log ''n'' search|journal=[[Communications of the ACM]]|date=1978|volume=21|issue=7|pages=550–553|doi=10.1145/359545.359557|doi-access=free}}</ref>

In practice, interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation. Its time complexity grows more slowly than binary search, but this only compensates for the extra computation for large arrays.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

=== 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" />

=== Generalization to graphs ===
Binary search has been generalized to work on certain types of graphs, where the target value is stored in a vertex instead of an array element. Binary search trees are one such generalization&mdash;when a vertex (node) in the tree is queried, the algorithm either learns that the vertex is the target, or otherwise which subtree the target would be located in. However, this can be further generalized as follows: given an undirected, positively weighted graph and a target vertex, the algorithm learns upon querying a vertex that it is equal to the target, or it is given an incident edge that is on the shortest path from the queried vertex to the target. The standard binary search algorithm is simply the case where the graph is a path. Similarly, binary search trees are the case where the edges to the left or right subtrees are given when the queried vertex is unequal to the target. For all undirected, positively weighted graphs, there is an algorithm that finds the target vertex in <math>O(\log n)</math> queries in the worst case.<ref>{{cite conference|last1=Emamjomeh-Zadeh|first1=Ehsan|last2=Kempe|first2=David|last3=Singhal|first3=Vikrant|title=Deterministic and probabilistic binary search in graphs|date=2016|pages=519–532|conference=48th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|arxiv=1503.00805|doi=10.1145/2897518.2897656}}</ref>

=== Noisy binary search ===
[[File:Noisy binary search.svg|thumb|right|In noisy binary search, there is a certain probability that a comparison is incorrect.]]
Noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array. For each pair of elements, there is a certain probability that the algorithm makes the wrong comparison. Noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position. Every noisy binary search procedure must make at least <math>(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}</math> comparisons on average, where <math>H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)</math><!-- Attribution of LaTeX code: see history of https://en.wikipedia.org/wiki/Binary_entropy_function --> is the [[binary entropy function]] and <math>\tau</math> is the probability that the procedure yields the wrong position.<ref>{{cite conference |last1=Ben-Or |first1=Michael |last2=Hassidim |first2=Avinatan |title=The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) |date=2008 |book-title=49th [[Annual IEEE Symposium on Foundations of Computer Science|Symposium on Foundations of Computer Science]] |pages=221–230 |doi=10.1109/FOCS.2008.58 |url=http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |archive-date=2022-10-09 |url-status=live |isbn=978-0-7695-3436-7}}</ref><ref name="pelc1989">{{cite journal|last1=Pelc|first1=Andrzej|title=Searching with known error probability|journal=Theoretical Computer Science|date=1989|volume=63|issue=2|pages=185–202|doi=10.1016/0304-3975(89)90077-7|doi-access=free}}</ref><ref>{{cite conference|last1=Rivest|first1=Ronald L.|last2=Meyer|first2=Albert R.|last3=Kleitman|first3=Daniel J.|last4=Winklmann|first4=K.|author-link1=Ronald Rivest|author-link2=Albert R. Meyer|author-link3=Daniel Kleitman|title=Coping with errors in binary search procedures|conference=10th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|doi=10.1145/800133.804351|doi-access=free}}</ref> The noisy binary search problem can be considered as a case of the [[Ulam's game|Rényi-Ulam game]],<ref>{{cite journal|last1=Pelc|first1=Andrzej|title=Searching games with errors—fifty years of coping with liars|journal=Theoretical Computer Science|date=2002|volume=270|issue=1–2|pages=71–109|doi=10.1016/S0304-3975(01)00303-6|doi-access=free}}</ref> a variant of [[Twenty Questions]] where the answers may be wrong.<ref>{{Cite journal | last1=Rényi | first1=Alfréd | title=On a problem in information theory | language=hu | mr=0143666 | year=1961 | journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei| volume=6 | pages=505–516}}</ref>

=== Quantum binary search ===
Classical computers are bounded to the worst case of exactly <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> iterations when performing binary search. [[Quantum algorithm]]s for binary search are still bounded to a proportion of <math display="inline">\log_2 n</math> queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for a lower time complexity on [[quantum computing|quantum computers]]. Any ''exact'' quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> queries in the worst case, where <math display="inline">\ln</math> is the [[natural logarithm]].<ref>{{cite journal|last1=Høyer|first1=Peter|last2=Neerbek|first2=Jan|last3=Shi|first3=Yaoyun|s2cid=13717616|title=Quantum complexities of ordered searching, sorting, and element distinctness|journal=[[Algorithmica]]|date=2002|volume=34|issue=4|pages=429–448|doi=10.1007/s00453-002-0976-3|arxiv=quant-ph/0102078}}</ref> There is an exact quantum binary search procedure that runs in <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> queries in the worst case.<ref name="quantumalgo">{{cite journal|last1=Childs|first1=Andrew M.|last2=Landahl|first2=Andrew J.|last3=Parrilo|first3=Pablo A.|s2cid=41539957|title=Quantum algorithms for the ordered search problem via semidefinite programming|journal=Physical Review A|date=2007|volume=75|issue=3|at=032335|doi=10.1103/PhysRevA.75.032335|arxiv=quant-ph/0608161|bibcode=2007PhRvA..75c2335C}}</ref> In comparison, [[Grover's algorithm]] is the optimal quantum algorithm for searching an unordered list of elements, and it requires <math>O(\sqrt{n})</math> queries.<ref>{{cite conference |last1=Grover |first1=Lov K. | author-link=Lov Grover | title=A fast quantum mechanical algorithm for database search | conference=28th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |pages=212–219|date=1996| location=Philadelphia, PA | doi=10.1145/237814.237866| arxiv=quant-ph/9605043}}</ref>