Jump to content

Uniform binary search

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Gnewf (talk | contribs) at 05:25, 7 July 2006 (I went ahead and MOVED the C impl to talk page because it was somewhat BROKEN: at the very least, it didn't work in trivial case of arrays with 1 element; didn't check for -1 return value in main()). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth's The Art of Computer Programming. 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

References

Retrieved from "https://en.wikipedia.org/w/index.php?title=Uniform_binary_search&oldid=62504757"