Login
Login

Multiplicative binary search

{{short description|Binary search variation with simplified midpoint calculation}}

{{technical|date=September 2017}}

{{Infobox algorithm

|class=Search algorithm

|image=Multiplicative Binary Search Depiction.svg

|caption=Visualization of the multiplicative binary search algorithm where 7 is the target value.

|data=Array

|time=O(log n)

|space = O(1)

|best-time=O(1)

|average-time=O(log n)

|optimal=Yes

}}

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.{{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}}

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.{{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}}{{cite tech 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}}

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 A0 ... An−1, and target value T, the following subroutine uses a multiplicative binary search to find the index of T in A.

  1. Set i to 0
  2. if i ≥ n, the search terminates unsuccessfully.
  3. if Ai = T, the search is done; return i.
  4. if Ai > T, set i to 2×i + 1 and go to step 2.
  5. if Ai < 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

{{Reflist}}

Category:Search algorithms