Multiplicative binary search: Difference between revisions

Revision as of 08:15, 19 February 2022

Latest revision as of 14:35, 17 February 2025

(3 intermediate revisions by 3 users not shown)

Line 11:

|best-time=[[big O notation#Orders of common functions|''O''(1)]]

|average-time=[[big O notation#Orders of common functions|''O''(log ''n'')]]

|optimal=Yes

}}

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

In [[computer science]], '''multiplicative binary search''' (also known as '''Eyztinger binary search'''<ref>{{cite journal |first1=Paul-Virak |last1=Khuong |first2=Pat |last2=Morin |title=Array Layouts for Comparison-Based Searching |journal=ACM Journal of Experimental Algorithmics |volume=22 |issue=1.3 |pages=1-39 |year=2017 |doi=10.1145/3053370 |url=https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf}}</ref><ref>{{cite web |first=Sergey |last=Slotkin |title=Eytzinger Binary Search |website=Algorithmica |date= March 2020 |url=https://algorithmica.org/en/eytzinger}}</ref>) 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|url=https://archive.org/details/datastructuretec0000stan|url-access=registration|publisher=Addison-Wesley|year=1980|chapter=Chapter 4.2.2: Ordered Table Search|pages=[https://archive.org/details/datastructuretec0000stan/page/136 136–141]|isbn=978-0201072563}}</ref>

Line 19 ⟶ 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 ==

Line 36 ⟶ 37:

* {{SDlink|Binary search tree}}

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

* {{SDlink|Ahnentafel}} developed by [[Michaël Eytzinger]] in 1590.

== Citations ==