Binary Search

Benchmark created by Oliver Morgan on

Setup

Array.prototype.binarySearchFast = function(search) {
      
    var size = this.length,
        high = size -1,
        low = 0;
    
    while (high > low) {
      
      if (this[low] === search) return low;
      else if (this[high] === search) return high;
  
      target = (((search - this[low]) / (this[high] - this[low])) * (high - low)) >>> 0;
  
      if (this[target] === search) return target;
      else if (search > this[target]) low = target + 1, high--;
      else high = target - 1, low++;
    }
    
    return -1;
  };
  
  Array.prototype.binarySearch = function(find) {
    var low = 0, high = this.length - 1,
        i, comparison;
    while (low <= high) {
      i = Math.floor((low + high) / 2);
      if (this[i] < find) { low = i + 1; continue; };
      if (this[i] > find) { high = i - 1; continue; };
      return i;
    }
    return null;
  };
  
  for (var i = 0, arr = [], find = 0; i < 100000; i += 100) {
    arr.push(i + Math.round(Math.random() * 100));
  }
  
  var find = arr[Math.round(arr.length * Math.random())];

Test runner

Ready to run.

Testing in
TestOps/sec
binarySearchFast
arr.binarySearchFast(find);
ready
binarySearchSlow
arr.binarySearch(find);
ready
indexOf
arr.indexOf(find);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.