binary-search

binary-search.js

/**
 * Performs a binary search on the provided *sorted* list and returns the index of the item if found. If it can't be found it'll return -1.
 *
 * @param {*[]} sorted (ascending) list Items to search through.
 * @param {*} item The item-value to look for.
 * @return {Number} The index of the item if found, -1 if not.
 */
function binarySearch(list, searchValue) {
    var minIndex = 0;
    var maxIndex = list.length - 1;
    var halfwayIndex;
 
    // Loop through)
    while (minIndex <= maxIndex) {
        // Grab the middle array index for comparison to search value
        halfwayIndex = Math.floor((minIndex + maxIndex) / 2);
 
        // Test if guess is equal to search value, return if true
        if (list[halfwayIndex] === searchValue) {
            return halfwayIndex;
        }
        else {
            
            if (searchValue > list[halfwayIndex]) {
                // The array was sorted, so if the guessIndex-value is less than the search-value, 
                // we know a match can only exist on higher indexes.  Thus we reassign minIndex to guessIndex+1
                minIndex = halfwayIndex + 1;
            }
            else {
                // The array was sorted, so if the guessIndex-value is more than the search-value, 
                // we know a match can only exist on lower indexes.  Thus we reassign minIndex to guessIndex-1
                maxIndex = halfwayIndex - 1;
            }
        }
    }
    return -1;
}