Uniform binary search

Uniform binary search is an optimization of the classic binary search algorithm.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

  • ไทยการค้นหาแบบทวิภาคอย่างมีเอกรูป
  • Italianoricerca dicotomica uniforme
  • Españolbúsqueda binaria uniforme
  • Englishuniform binary search
  • فارسیجستجوی دودویی یکپارچه

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

Uniform binary search is an optimization of the classic binary search algorithm. It was first published by Donald Knuth, in The Art of Computer Programming, who credited its idea to Ashok K. Chandra.

It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth's MIX) on which *a table lookup is generally faster than an addition and a shift, and *many searches will be performed on the same array, or on several arrays of the same length

Uniform binary search is an optimization of the classic binary search algorithm. It was first published by Donald Knuth, in The Art of Computer Programming, who credited its idea to Ashok K. Chandra.

It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth's MIX) on which a table lookup is generally faster than an addition and a shift, and many searches will be performed on the same array, or on several arrays of the same length

C implementation

The uniform binary search algorithm looks like this, when implemented in C. define LOG_N 4 static int delta[LOG_N]; void make_delta(int N) { int power = 1; int i = 0; do { int half = power; power

An implementation of Knuth's algorithm in Pascal, by Han de Bruijn An implementation of Knuth's algorithm in Go, by Adrianus Warmenhoven

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

Provenance

snapshot enwiki-001317369338 · captured 1760721715.0 · version history

Cite this page as: encyclopegia.org, “Uniform binary search”, snapshot enwiki-001317369338. https://encyclopegia.org/a/uniform-binary-search

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.