Algorithms - Binary Search

binarySearch.js

/*
    Binary search 
    - Time complexity O(logn)
    - Array needs to be sorted for binary search to work
*/

function binarySearch(arr, target){
    // Define left, right and middle pointers
    let left = 0;
    let right = arr.length - 1;
    // Middle pointer - right + left / 2
    let middle = Math.floor((right + left) / 2);
    // While target is not matched and left is less than or equal to right pointer
    while (arr[middle] !== target && left <= right) {
        // If middle value is less than target shift left pointer to middle + 1
        // because middle is already not the value
        if (arr[middle] < target) left = middle + 1;
        // Else middle value is more than target shift right pointer to middle - 1
        // because middle is already not the value
        else right = middle - 1;
        // Recalculate middle pointer
        middle = Math.floor((right + left) / 2);
    }
    // If middle value is target return middle else return -1 for not found
    return arr[middle] === target ? middle : -1;
}

// binarySearch([1,2,3,4,5],2) // 1
// binarySearch([1,2,3,4,5],3) // 2
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 95) // 16