Array.prototype.binarySearch = function binarySearch(find, comparator) { var low = 0, high = this.length - 1, i, comparison; while (low <= high) { i = parseInt((low + high) / 2, 10); comparison = comparator(this[i], find); if (comparison < 0) { low = i + 1; continue; }; if (comparison > 0) { high = i - 1; continue; }; return i; } return null; };
Extending Array with this binarySearch method allows you to re-use the functional arguments to passed to sort to generate the sorted array in the first place.
Should the title be “Binary *search* an array in JavaScript”?
January 21st, 2009
There is example of using search array functionality
http://vitana-group.com/article/javascript-dhtml/Iterator
as described here it supports any array items type, even array of json objects
Looks good
April 8th, 2010
i = parseInt((low + high) / 2, 10); ????
What’s wrong with i = Math.floor((low + high) / 2); ? parseInt has to turn the math result to a string, and then back to a number again, which wastes a lot of time.
July 5th, 2010
Well, since I’ve already tossed my hat in, it occurs to me that the return for a failed search should be -1, which stays with the pattern established by String.indexOf. Since null is not a number, and every other possible result of the function is a number, you really ought to stay with numbers rather than tossing in null.
July 5th, 2010
Oh, one more thing:
is redundant.
works just fine.
July 5th, 2010