<< Algorithms

Binary search is useful for when a list is already sorted. This is because it splits the list into 2 parts and ignores one half of the list. It compares the item to look for with the middle element and depending on whether the middle element is larger or smaller, the algorithm will ignore the other half of the list. It first checks if the middle element is equal to the item to search for. If the item to search for is greater than the middle element then it knows that it must be in the greater half of the list and vica versa. It has a time complexity of O(log(n)).

				function binarySearch(arr, x){
    var left = 0;
    var right = arr.length - 1;

    while(left <= right){
    var midpoint = Math.floor((left + right) / 2); 

    if(x == arr[midpoint]){
        return midpoint;
    }
    else if(x < arr[midpoint]){
        right = midpoint - 1;
    }
    else {
        left = midpoint + 1;
    }
    return -1;
    }
}