Array.prototype.binarySearch = function(find, comparator) {
  var low = 0, high = this.length - 1,
      i, comparison;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    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.

7 Comments

  1. noah

    Should the title be “Binary *search* an array in JavaScript”?

  2. John

    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

  3. Jim Hawk III

    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.

  4. Jim Hawk III

    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.

  5. Jim Hawk III

    Oh, one more thing:

    Array.prototype.binarySearch = function binarySearch(find, comparator)

    is redundant.

    Array.prototype.binarySearch = function (find, comparator)

    works just fine.

  6. bob

    the “continue”s are unnecessary if you just use if/else

    if (comparison < 0)
    low = i + 1;
    else if (comparison > 0)
    high = i – 1;
    else
    return i;

  7. Peter Wone

    It is often more useful to return the termination index. You can use this to retrieve, or to insert in order.

Leave a Comment

Enclose code in <code lang="ruby"></code> if you care.
Preview your comment using the button below.