Multiplicative binary search: Difference between revisions

Revision as of 01:15, 5 March 2017

Revision as of 19:02, 5 March 2017

Line 12:

In [[computer science]], '''multiplicative binary search''' is a variation

of [[binary search algorithm|binary search]] that uses a specific permutation of keys in an array instead of the sorted order used by regular binary

search.<ref>{{cite book|first=Thomas A.|last=Standish|title=Data Structure Techniques|publisher=Addison-Wesley|year=1980|chapter=Chapter 4.2.2: Ordered Table Search|pages=136-141136–141|isbn=978-0201072563}}</ref>

Multiplicative binary search was first described by Thomas Standish in 1980.

This algorithm was originally proposed to simplify the mid-pointmidpoint index calculation on small computers without efficient division or shift operations, but its [[cache (computing)|cache]]-friendly nature makes it suitable for out-of-memory static search on [[Block (data storage)|block-oriented]] storage as an alternative to [[B+ tree|B+ trees]]s.

Multiplicative binary search is used by some [[optimizing compiler|optimizing compilers]]s to implement [[switch statement|switch statements]]s.<ref>{{cite journal |last1=Sayle|first1=Roger A. |title=A Superoptimizer Analysis of Multiway Branch Code Generation |journal=Proceedings of the GCC Developers’ Summit |date=17 June 2008 |pages=103-116103–116 |url=https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf |accessdate=4 March 2017}}</ref><ref>{{cite techreport | first=David A. | last=Spuler | title=Compiler Code Generation for Multiway Branch Statements as a Static Search Problem | number=94/03 | institution=Department of Computer Science, James Cook University, Australia | date=January 1994}}</ref>

== Algorithm ==

Line 28:

# if A_''i'' < ''T'', set ''i'' to 2×''i'' + 1 and go to step 2.

# if A_''i'' > ''T'', set ''i'' to 2×''i'' + 2 and go to step 2.

== See also ==