Binary Search

Intro

Binary search is an efficient divide-and-conquer algorithm for finding an item from a sorted list of items.
It has a time complexity of O(n log n).

Binary Search - How does it work?

Binary search is a divide-and-conquer algorithm. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

It is faster than the Linear search since after every step it discards half of the input dataset.

It is important to note that this algorithm works only when we provide the sorted input dataset. So if we have an unsorted list and want to use a Binary search, we need to sort it first.

Let's implement it to better understand it.

Implementation of the Binary Search

We'll cover both the iterative and recursive approaches. We'll code everything in Java.

Iterative

public class BinarySearch {

    public int search(int[] arr, int element) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (high + low) / 2;

            if (arr[mid] == element) {
                return mid;
            }

            if (element < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }
}

Here, we first define two variables low and high. Then, inside the while loop, we find the mid element and we check if the element that we are looking for is equal to the mid element. If yes, we return the index and finish with the process.

If not, then we check if the given element is smaller than the middle element. If yes, we set the high to be mid - 1. With this, we are discarding all elements greater than the middle element, including the middle element.
If not, we are setting the low to mid + 1. In this case, we are discarding all elements smaller than mid, including the middle element itself.

We are looping through until we find the element or the low becomes greater than high, which would mean that the element is not present in the provided dataset.

Recursive

public class BinarySearch {

    public int search(int[] arr, int low, int high, int element) {
        if (high >= low) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == element) {
                return mid;
            }

            if (element < arr[mid]) {
                return search(arr, low, mid - 1, element);
            } else {
                return search(arr, mid + 1, high, element);
            }
        }

        return -1;
    }
}

Here, we recursively call the method search until we find the element or return -1 if the element is not present.

Binary search - analysis

Binary search has the worst case and average case time complexity of O(n log n) and the best case of O(1).

Worst and average cases O(n log n) - When the algorithm is using the divide and conquer approach, we know that there will be fewer iterations compared to the O(n) - where we need to touch every element in the dataset.
These algorithms usually discard one portion of the dataset after every iteration, so the time complexity is O (n log n).

Best case O(1) - In case the element that we are looking for is actually the middle element of the provided sorted dataset.

Space Complexity is O(1).

Advantages:

• Binary search is faster than linear search, especially for large arrays. 
• More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search. 
• Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.

Drawbacks:

• The array should be sorted. 
• Binary search requires that the data structure being searched be stored in contiguous memory locations. 
• Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered.