Binary Search

Fastest way to find a number

by shanimal

HTML

<div id="target"></div>

JavaScript

var a = new Array(3000000).fill(1);
var haystack = a.map(function(v, i) {return i});
var start = performance.now();
for (var i in haystack) {
    findNeedleInSortedHayStack(haystack[i], haystack);
}
log(performance.now() - start)

/**
    Uses Binary Search to find the needle in the haystack
    @param * needle: the element to search for
    @param Array haystack: the list to search
    @returns index of element or -1 if not found
 */
function findNeedleInSortedHayStack(needle, haystack) {

    var min = 0,
        mid,
        max = haystack.length - 1,
        val;

    while (min <= max) {
        mid = max + min >> 1;
        val = haystack[mid];
        if (val < needle) {
            // move right
            min = mid + 1;
        } else if (val > needle) {
            // move left
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;

}

/**
		Logs parameters to the target div, will throw error if passes cyclic object
    Add Crockford's decycler if you need to display cyclic objects
    https://raw.githubusercontent.com/douglascrockford/JSON-js/master/cycle.js
 */
function log(){
    document.getElementById('target').innerHTML += Array.prototype.slice.call(arguments).map(function (v) { 
        return JSON.stringify(v);
    }).join(' ') + "<br/>";
}