Searching JavaScript arrays with a binary search

JavaScript performance comparison

Revision 10 of this test case created

Info

A binary search searches by splitting your array into smaller and smaller chunks until it finds your desired value. Unlike the normal indexOf which searches from left to right in a simple iteration. The binary search Wikipedia article explains it best (as always). There are a couple of downsides; It will be slower with smaller data sets (this needs proving) and the array you are searching needs to be sorted.

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    /**
     * Performs a binary search on the host array. This method can either be
     * injected into Array.prototype or called with a specified scope like this:
     * binaryIndexOf.call(someArray, searchElement);
     *
     * @param {*} searchElement The item to search for within the array.
     * @return {Number} The index of the element which defaults to -1 when not found.
     */

    function binaryIndexOf(searchElement) {
        'use strict';
   
        var minIndex = 0;
        var maxIndex = this.length - 1;
        var currentIndex;
        var currentElement;
        var resultIndex;
   
        while (minIndex <= maxIndex) {
                resultIndex = currentIndex = (minIndex + maxIndex) / 2 | 0;
                currentElement = this[currentIndex];
   
                if (currentElement < searchElement) {
                        minIndex = currentIndex + 1;
                }
                else if (currentElement > searchElement) {
                        maxIndex = currentIndex - 1;
                }
                else {
                        return currentIndex;
                }
        }
   
        return ~maxIndex;
    }
   
    Array.prototype.binaryIndexOf = binaryIndexOf;
   
    for (var testArray=[],i=0;i<10000;++i) testArray[i]=i;
   
    function shuffle(array) {
      var tmp, current, top = array.length;
      if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
   
    function linearIndexOf(entry) {
      for (var i = 0, l = testArray.length; i < l; i++) {
        if (testArray[i] === entry) {
          return i;
        }
      }
      return -1;
    }
    testArray = shuffle(testArray).sort();
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
binaryIndexOf
testArray.binaryIndexOf(3)
testArray.binaryIndexOf(5)
testArray.binaryIndexOf(10)
testArray.binaryIndexOf(101)
testArray.binaryIndexOf(500)
pending…
indexOf
indexOf(3)
indexOf(5)
indexOf(10)
indexOf(101)
indexOf(500)
pending…
linearIndexOf
linearIndexOf(3)
linearIndexOf(5)
linearIndexOf(10)
linearIndexOf(101)
linearIndexOf(500)
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment