Binary Search Algorithm

While working with Linear Search, we observed that we are not using any information about the data in the input.

For example, consider the input is already sorted. Then, we can use this information to calculate an approximate index that might have the key value.

Binary Search is one of the most commonly used search algorithms that take inspiration from our day-to-day lives. For example, consider a scenario where you need to search for a word in a dictionary. How do you do it?

It is highly unlikely that you will start from the first page and follow along every single page until you reach the page where the word is present.

The general approach is to open the dictionary at any random page and then move to the left or right of the current page based on the key we are looking for. Then, repeat this process by opening the approximate half in either direction, ignoring the other half.

This approach helps us to reduce the total search space by half (approximately) in every iteration and thus is more efficient as compared to going through every single page from start to end (or until the key is found)

From the premise mentioned above, we can understand that the algorithm will only work if the input is sorted. If the input is NOT sorted, we can not decide which direction to choose as the key can be in any of the two halves.

Following is a simple java implementation of the binary search algorithm:

public int search(int[] input, int key){
    int start = 0, end = input.length - 1;

    // compare till start <= end to include 
    // the last standing element as well
    while(start <= end){
        int mid = (start + end) / 2;
        if(key == input[mid]){
            return mid;
        } else if(key < input[mid]){
            end = mid - 1;
        } else{
            start = mid + 1;
        }
    }
    return -1;
}

Assuming the input is already sorted, we start by calculating the mid index value and then checking if it holds the key. If yes, we return the index and terminate the loop. Otherwise, we compare the value at the mid index with the key and update the search space by updating the start or end accordingly.

The overall complexity of the binary search algorithm is \(O(log_2n)\) as it reduces the number of elements by half in every iteration.