Binary Search with uneven distribution (v12)

Revision 12 of this benchmark created by Oliver Caldwell 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;
    };
    
    /**
     * 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;
    }
    
    for (var i = 0, arr = [], find = 0; i < 100000; i += 100) {
      arr.push(i + Math.round(Math.random() * 100));
    }
    arr.push(100000000);
    
    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
binaryIndexOf
binaryIndexOf.call(arr, find);
ready

Revisions

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