Multiplicative binary search

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, multiplicative binary search is a variation of binary search that uses a specific permutation of keys in an array instead of the sorted order used by regular binary search. Multiplicative binary search was first described by Thomas Standish in 1980. This algorithm was originally proposed to simplify the midpoint index calculation on small computers without efficient division or shift operations. On modern hardware, the cache-friendly nature of multiplicative binary search makes it suitable for out-of-core search on block-oriented storage as an alternative to B-trees and B+ trees. 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 (root) block, regardless of block size. Multiplicative binary search is used by some optimizing compilers to implement switch statements.

In computer science, multiplicative binary search is a variation of binary search that uses a specific permutation of keys in an array instead of the sorted order used by regular binary search. Multiplicative binary search was first described by Thomas Standish in 1980. This algorithm was originally proposed to simplify the midpoint index calculation on small computers without efficient division or shift operations. On modern hardware, the cache-friendly nature of multiplicative binary search makes it suitable for out-of-core search on block-oriented storage as an alternative to B-trees and B+ trees. 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 (root) block, regardless of block size. Multiplicative binary search is used by some optimizing compilers to implement switch statements. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1276207828 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001276207828 · captured 1739799313.0 · version history

Cite this page as: encyclopegia.org, “Multiplicative binary search”, snapshot enwiki-001276207828. https://encyclopegia.org/a/multiplicative-binary-search

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.