Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Multiplicative binary search
open-in-new
<h2 id="algorithm">Algorithm</h2> <p>Multiplicative binary search operates on a permuted sorted array. Keys are stored in the array in a level-order sequence of the corresponding balanced <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a>. This places the first pivot of a binary search as the first element in the array. The second pivots are placed at the next two positions. </p><p>Given an array <i>A</i> of <i>n</i> elements with values <i>A</i>0 ... <i>A</i><i>n</i>−1, and target value <i>T</i>, the following <a href="/facts/Subroutine/9vFJrg0A">subroutine</a> uses a multiplicative binary search to find the index of <i>T</i> in <i>A</i>. </p> <ol><li>Set <i>i</i> to 0</li> <li>if <i>i</i> ≥ <i>n</i>, the search terminates unsuccessfully.</li> <li>if A<i>i</i> = <i>T</i>, the search is done; return <i>i</i>.</li> <li>if A<i>i</i> > <i>T</i>, set <i>i</i> to 2×<i>i</i> + 1 and go to step 2.</li> <li>if A<i>i</i> < <i>T</i>, set <i>i</i> to 2×<i>i</i> + 2 and go to step 2.</li></ol> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Binary_search_tree/gWubNt7b">Binary search tree</a> – Rooted binary tree data structure</li> <li><a href="/facts/Binary_tree/TDV7GMpu">Methods for storing binary trees</a> – Limited form of tree data structure</li> <li><a href="/facts/Ahnentafel/nlnFRK39">Ahnentafel</a> – Genealogical numbering system for listing a person's direct ancestors</li></ul> <h2 id="citations">Citations</h2> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Standish, Thomas A. (1980). "Chapter 4.2.2: Ordered Table Search". Data Structure Techniques. Addison-Wesley. pp. 136–141. ISBN 978-0201072563. <a href="978-0201072563" target="_blank">978-0201072563</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Sayle, Roger A. (17 June 2008). "A Superoptimizer Analysis of Multiway Branch Code Generation" (PDF). Proceedings of the GCC Developers' Summit: 103–116. Retrieved 4 March 2017. <a href="https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf" target="_blank">https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Spuler, David A. (January 1994). Compiler Code Generation for Multiway Branch Statements as a Static Search Problem (Technical report). Department of Computer Science, James Cook University, Australia. 94/03. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>