Multiplicative binary search: Difference between revisions

Revision as of 14:50, 22 May 2020

Latest revision as of 14:35, 17 February 2025

(5 intermediate revisions by 5 users not shown)

Line 20:

On modern hardware, the [[cache (computing)|cache]]-friendly nature of multiplicative binary search makes it suitable for [[out-of-core]] search on [[Block (data storage)|block-oriented]] storage as an alternative to [[B-tree]]s and [[B+ tree]]s. For optimal performance, the [[branching factor]] of a B-tree or B+-tree must match the block size of the [[file system]] that it is stored on. The permutation used by multiplicative binary search places the optimal number of keys in the first ([[Tree_(graph_theory)#Rooted_tree|root]]) block, regardless of block size.

Multiplicative binary search is used by some [[optimizing compiler]]s to implement [[switch statement]]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–116 |url=https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf |accessdate=4 March 2017}}</ref><ref>{{cite techreporttech report | 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 ==

Multiplicative binary search operates on a permuted sorted array. Keys are stored in the array in a level-order sequence of the corresponding balanced [[binary search tree]].

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.

Given an array ''A'' of ''n'' elements with values ''A''₀ ... ''A''_''n''−1, and target value ''T'', the following [[subroutine]] uses a multiplicative binary search to find the index of ''T'' in ''A''.

# Set ''i'' to 0

# if ''i'' ≥ ''n'', the search terminates unsuccessfulunsuccessfully.

# if A_''i'' = ''T'', the search is done; return ''i''.

# 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 ==

* [[{{SDlink|Binary search tree]]}}

* [[{{SDlink|Binary_tree#Methods_for_storing_binary_trees|Methods for storing binary trees]]}}

* [[{{SDlink|Ahnentafel]]}}

== Citations ==