Searching JavaScript arrays with a binary search vs. linear search

JavaScript performance comparison

Revision 7 of this test case created by Anton Lauridsen

Info

Performs a comparison of a binary search of an array vs. a linear search of an array of an element with a specific key.

Using a array with 50 elements

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, searchKey);
     *
     * @param {*} searchKey The item to search for within the array.
     * @return {Number} The index of the element which defaults to -1 when not found.
     */

   
    function binaryIndexOf(searchKey) {
      '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.key < searchKey) {
          minIndex = currentIndex + 1;
        } else if (currentElement.key > searchKey) {
          maxIndex = currentIndex - 1;
        } else {
          return currentIndex;
        }
      }
   
      return~ maxIndex;
    };
   
    /**
     * Performs a linear 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, searchKey);
     *
     * @param {*} searchKey The item to search for within the array.
     * @return {Number} The index of the element which defaults to -1 when not found.
     */

   
    function linearIndexOf(searchKey) {
      'use strict';
      for (var idx = 0, len = this.length; idx < len; idx++)
        if (this[idx].key === searchKey)
          return idx;
   
      return -1;
    };
    Array.prototype.binaryIndexOf = binaryIndexOf;
    Array.prototype.linearIndexOf = linearIndexOf;
   
    for (var testArray = [], i = 0; i < 50; ++i) testArray[i] = {
      key: i * 2,
      value: i
    };
};
</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(1)
testArray.binaryIndexOf(0)
testArray.binaryIndexOf(4)
pending…
linearIndexOf
testArray.linearIndexOf(1)
testArray.linearIndexOf(0)
testArray.linearIndexOf(4)
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