binaryIndexOf and indexOf

JavaScript performance comparison

Test case created by Oliver Caldwell

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  var source = [];
  
  /**
   * Fetches a random number between 0 and 100000.
   */
  function getRandomNumber() {

  	'use strict';
  	return Math.floor(Math.random() * 100000);
  }
  
  for (var i = 0; i < 100000; i++) {
  	source.push(getRandomNumber());
  }
  source.sort();
  var smallSource = source.slice(0, 20);
  var toFind = source[getRandomNumber()];
  var smallToFind = smallSource[Math.floor(Math.random() * 50)];
  
  
  
  /**
   * 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;
  
  	while (minIndex <= maxIndex) {
  		currentIndex = Math.floor((minIndex + maxIndex) / 2);
  		currentElement = this[currentIndex];
  
  		if (currentElement < searchElement) {
  			minIndex = currentIndex + 1;
  		}
  		else if (currentElement > searchElement) {
  			maxIndex = currentIndex - 1;
  		}
  		else {
  			return currentIndex;
  		}
  	}
  
  	return -1;
  }
  
  Array.prototype.binaryIndexOf = binaryIndexOf;

};
</script>

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
indexOf (100,000 items)
source.indexOf(toFind);
pending…
binaryIndexOf (100,000 items)
source.binaryIndexOf(toFind);
pending…
indexOf (50 items)
smallSource.indexOf(smallToFind);
pending…
binaryIndexOf (50 items)
smallSource.binaryIndexOf(smallToFind);
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.

0 Comments