Searching JavaScript arrays with a binary search

JavaScript performance comparison

Test case created by Alexey


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

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:
     *, 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();

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec

Compare results of other browsers


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.

Comment form temporarily disabled.

Add a comment