Blind Binary Search

by alexb

JavaScript

/**
 * Untested implementation of binary search following the rules outlined at:
 * https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
 *
 * I am aware that this algorithm is not guaranteed to return the index of
 * the first occurrence of the value in the array (if there are multiple
 * occurrences) but that behaviour is not specified in the challenge.
 *
 * This code has not been tested in the slightest. Who knows if there are bugs?
 */

function binary_search(arr, value) {
    var min = 0,
        max = arr.length - 1;
    
    while (max >= min) {
        var midpoint = min + Math.floor((max - min) / 2);
        
        if (arr[midpoint] == value) {
            return midpoint;
        }
        else if (arr[midpoint] > value) {
            max = midpoint - 1;
        }
        else {
            min = midpoint + 1;
        }
    }
    
    return -1;
}