Algorithms using Binary Search – A Java Implementation

Algorithms using Binary Search are some of the most popular algorithms in interviews as well as in some real life situations.

Searching for a piece of data in a data structure is a common recurring activity programmers do. The most common approach that comes to mind for searching is to traverse through the data structure and look at each element in sequence. If it matches with what we are searching for, we have a hit. This approach is known as Linear Search.

While this approach is good enough for small data-sets, it is brutally inefficient for large data-sets. The order for growth of Linear Search is O(n).

In most practical situations, we need something better. And that’s where Binary Search comes into the picture.

In this post, we will look at Binary Search as well as some Algorithms using Binary Search and their implementations in Java.

What is Binary Search?

The premise of Binary Search is to reduce the search space. It works by repeatedly dividing the search space into half and then searching in the half where the element is expected to be present.

Naturally, to decide which half of the array to search, the array should be sorted. Also, the repeated process of dividing an array into two halves allows us to perform Binary Search recursively.

Below is the algorithm for Binary Search:

• Compare X (the element to be searched) with the middle element in the array.
• If X matches the middle element, return the middle element index.
• If X is greater than the mid element, it can only be present in the right half of the array. So we recur the process for the right half.
• If X is lesser than the mid element, it can only be present in the left half of the array. So we recur the process for the left half.

Since we are recursively dividing the array on each iteration, Binary Search runs in O(log n) time complexity. This is much better than O(n) time complexity in Linear Search.

Binary Search Java Implementation

Below is an implementation of the above Binary Search algorithm in Java.

public int performBinarySearch(int[] array, int beg, int end, int searchElement){
        if (end < beg)
            return -1;

        int mid = (beg + end)/2;

        if(array[mid] == searchElement)
            return mid;

        if(array[mid] > searchElement)
            return performBinarySearch(array, beg, mid-1, searchElement);

        if(array[mid] < searchElement)
            return performBinarySearch(array, mid+1, end, searchElement);

        return -1;
}

Basically, this method runs recursively. At each step, we compare the middle element of the array with the Search Element. If there is a match, we return the index. Else we move to right or left sub-array depending on the comparison of the Search Element with the middle element.

Find Occurrence of Element in Sorted Array

Another interesting problem that lends itself well to Binary Search is to find the number of occurrences of an element in a sorted array.

Consider a sorted array as below. Here we have to find the occurrence of the element 2. As you can see, 2 is occurring 4 times.

The first approach to solve this problem could be a simple Linear Search. Traverse through the array. Increment a counter each time you find the element 2. At the end of the array traversal, you will have the count.

The complexity of such an algorithm would be O(n).

We can do better if we use Binary Search to solve this problem. Below is an algorithm using Binary Search to solve the above problem.

• Find the index of the first occurrence of the Search Element X using Binary Search
• Find the index of the last occurrence of the Search Element X using Binary Search
• Return (Last Index – First Index) + 1 as the count of the number of occurrences.

Binary Search runs in time complexity of O(log n). We have two iterations of Binary Search running in this algorithm making it 2* log n. However, the overall complexity is still O(log n).

Below is a Java implementation for the above algorithm.

Find First Index

Basically, here we use the Binary Search approach to find the first index. The only difference is while comparing array[mid] with the Search Element we check a couple of extra conditions to make sure if we are actually at the first occurrence.

private int findFirstIndex(int[] array, int beg, int end, int searchElement){

        if(end < beg)
            return -1;

        int mid = (beg + end)/2;

        if(array[mid] == searchElement && (mid == 0 || array[mid-1] < searchElement))
            return mid;
        else if(array[mid] >= searchElement)
            return findFirstIndex(array, beg, mid-1, searchElement);
        else
            return findFirstIndex(array, mid+1, end, searchElement);
}

Find Last Index

We also find the Last Index using Binary Search. Again, we use a similar condition to verify whether we are really at the last occurrence of the element to be found.

private int findLastIndex(int[] array, int beg, int end, int searchElement){

        if(end < beg)
            return -1;

        int mid = (beg + end)/2;

        if(array[mid] == searchElement && (mid == end || array[mid+1] > searchElement))
            return mid;
        else if(array[mid] <= searchElement)
            return findLastIndex(array, mid+1, end, searchElement);
        else
            return findLastIndex(array, beg, mid-1, searchElement);
}

Find Count Method

Lastly, we implement a method to take the first index and the last index and return the number of occurrences.

public int countNumberOfOccurrences(int[] array, int searchElement){

        int first = findFirstIndex(array, 0, array.length-1, searchElement);

        int last = findLastIndex(array, 0, array.length-1, searchElement);

        return (last-first) + 1;

}

Find an Element in Sorted and Rotated Array

The next interesting problem is finding an element in a sorted and rotated array.

Consider the below array as an example:

Here, we want to search the element 4 and find its index. However, the array has been sorted and then rotated. That’s why the elements 10 & 20 are present in the beginning half.

Again, a typical approach is to perform Linear Search. However, this problem can also be solved using Binary Search in O(log n) time complexity.

The trick here is to find the Pivot point of the array and then apply Binary Search to the appropriate sub-array. In the above example the pivot point is index 1 (element 20). Below is an algorithm to solve it.

• Find Pivot Point using Binary Search. Basically, pivot point is the element in the array for which the next element is smaller
• If Search Element X is greater than first element in the array, then search in left sub-array using Binary Search
• Else if Search Element X is lesser than last element in the array, then search in right sub-array using Binary Search.

Below is the Java implementation for the above algorithm.

Find Pivot Point

First step is to find the Pivot Point recursively. Important point is to check the next element to the mid element to make sure we have reached the Pivot Point.

private int findPivotIndex(int[] array, int beg, int end){
        if(end < beg)
            return -1;

        int mid = (beg + end)/2;

        if(mid < end && array[mid] > array[mid+1])
            return mid;
        else if(mid > beg && array[mid] < array[mid-1])
            return mid-1;
        else if(array[mid] <= array[beg])
            return findPivotIndex(array, beg, mid-1);
        else
            return findPivotIndex(array, mid+1, end);
}

Perform Binary Search on the Appropriate Sub-Array

Once we have the pivot element, we can perform Binary Search on either the left or the right sub-array as below.

public int findElementInSortedRotatedArray(int[] array, int searchElement){
        int pivot = findPivotIndex(array, 0, array.length-1);

        if (pivot == -1)
            return performBinarySearch(array, 0, array.length-1, searchElement);

        if(array[pivot] == searchElement)
            return pivot;

        if(array[0] <= searchElement)
            return performBinarySearch(array, 0, pivot, searchElement);

        return performBinarySearch(array, pivot+1, array.length-1, searchElement);

}

Here, we leverage the performBinarySearch() method we discussed in the earlier section.

Conclusion

In this post, we looked at various Algorithms using Binary Search and implemented those in Java. This is just a small subset of the type of problems you can solve using Binary Search.

Binary Search is highly efficient for sorted arrays and has wide variety of applications. However, the basic concept remains the same.

If you have any comments or queries, do sound off in the comments section below.

Happy Learning!