Searching JavaScript arrays with a binary search

JavaScript performance comparison

Test case created by Alexey

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<4000;++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;
    }
   
    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
testArray.indexOf(3)
testArray.indexOf(5)
testArray.indexOf(10)
testArray.indexOf(101)
testArray.indexOf(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:

1 comment

Anton Lauridsen commented :

I believe the question is not as simple as portrayed. If the array contains a more complex object, e.g. a map with a key, value property and the search is performed by key then you get a lot more varied results, depending on the browser.

If the array is samll, less than 50 elements, a binary search will have a poorer performance on some browsers, the exact cutoff where a binary search is more efficient varies from browser to browser.

I have added a test case to illustrate this.

Add a comment