Wednesday, August 15, 2012

Uniform Binary Search Implementation in JavaScript

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

Just simply implemented in JS from original C source of Knuth's algorithm.


// target = [91, 97, 99, 101, 127, 129, 145]
// will found index of 127 via optimized bin search algo.

thinking...
-----------------
middle of target: 3
127 is bigger than 101
127 is less than 129
127 at index: 4

Source: http://jsfiddle.net/VCtqD/1/

No comments:

Post a Comment