Binary search algorithm

Tags: , , ,

Binary search algorithm

The binary search algorithm is a very known algorithm and taught in the basics of computer science algorithm class. It is simple algorithm however, it is very powerful one, can be used to solve many problems.  A classic example of the application of the binary search algorithm is searching for a word in dictionary.  What process do you follow? That’s exactly everything about BSA.

Let’s understand what is a binary search algorithm in programming terms. Given a sorted array of integers, find a key or a number or an element in that sorted array.

Binary search algorithm : Thought process

Before coming up with any solution, the first question is what should be output if a key does not exist in array? What happens if there are duplicate integers in array, which index should be returned? Maybe it is good to as for data size, range, and nature of data before rushing into any solution. Once, you have this information, you are better equipped to solve the problem right.

Assuming that you have no knowledge of binary search algorithm, how would you that?

Brute force or simple method would be to go through all elements of an array and compare them with key, once key matches any element, we return the index saying the key was found at that index. Simple isn’t it? How many comparisons you have to make in the worst-case scenario? Yes, it will be equal to the number of elements in array to be searched. In big O notation, the worst complexity of the brute force method will be O(N), which occurs when either searched key is not there in array at all or it is at the end of an array.

How can we improve worst-case complexity of simple search? What information given in the problem statement we have not yet used? We did not consider the fact that the array is sorted.

The second question is how can we use that information? Since the array is sorted, we already know that for any element of the array at index i, all elements on left of i, from start to i-1 will be smaller and all elements on the right of i, from i+1 to end will be greater than it. But how does it help us?

In a brute force solution, we started with the first element and went all the way to the last element comparing each one with key to be found. Can we start randomly from anywhere and see where would key to be found may be located in an array based on condition described. The optimum solution would be to start from mid.

Start at mid and see if A[mid] is what you are looking for? If yes, great! return mid. But if it not what you are looking for then key can be anywhere in array. How can you decide if you have to search in the left part of the mid or right part of the array? That’s where sorted property of array comes to help! If A[mid] < key, that means,  key must not be before mid. So, we discard array[start..mid] and only look for key in remaining part of array that is A[mid+1..end].
Similarly, if A[mid] > key , key cannot be after mid, hence we can discard right subarray A[mid..end] and look for key in A[start..mid-1].

So when do we call that key is not present? When the size of array goes less than one, where start > end, and we have not found the key, we can say that key is not present at all in the array.

Let’s take an example and see how it works! We have an array as shown below and we are looking for key 10:

First, find mid of array, it is index 4 = 0+9/2

Next, is A[mid] is equal to the key? Nope. Is key greater than A[mid]? Yes. What do we do? We focus on the right part of array from mid and discard left subarray.

The new start is index 5. Find mid of new reduced array, which will be 7 = ( 5 + 9 ) /2. Is A[mid] == key? No, is key greater than key? No, hence, discard right subarray and search in left subarray.

New end of array is 6 and start is 5. Find new mid which is 5. Is A[5] == key? No. Is key greater A[mid]? Yes, then discard left subarray and focus on right subarray.

At this point, end = start = 6, hence mid = 6. Is A[mid] == key? Yes, hence return mid index.

I hope this example made it clear how the binary search algorithm works. Can you draw execution flow if the key to be searched is let’s say 5?

Now that we have learned algorithms and solved a couple of examples, it’s time to implement the algorithm.

Binary search algorithm implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    public static int binarySearchIterative(int[] a, int start, int end, int key){

        while(start <= end) {
            int mid = start + (end - start)/2;

            /*Check if element at mid index
            element we are looking for? If yes, return mid*/
            if(a[mid] == key) return mid;

            /*
            If the element at mid is not equal to key
            what is relationship between A[mid] and key?
            If A[mid] > key, we look in left subarray
            else we look into right subarray
             */
            if(a[mid] > key){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

        int index = binarySearchIterative(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Recursive implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {
    public static int binarySearchRecursive(int[] a, int start, int end, int key){

        if (start <= end) {
            int mid = start + (end - start)/2;

            /*Check if element at mid index
            element we are looking for? If yes, return mid*/
            if(a[mid] == key) return mid;

            /*
            If the element at mid is not equal to key
            what is relationship between A[mid] and key?
            If A[mid] > key, we look in left subarray
            else we look into right subarray
             */
            if(a[mid] > key){
                return binarySearchRecursive(a,start, mid-1, key);
            }else{
                return binarySearchRecursive(a,mid+1, end, key);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

        int index = binarySearchIterative(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

What will be the complexity of the binary search algorithm? It is O(log N). Please follow this link to understand more how does it happen.
Worst case complexity of binary search tree

It’s also important to explain that recursive implementation takes more space than it seems. Since, each function call puts a stack frame on stack, it will take O(log N) stack frames. So, when you are dealing with a huge chunk of data in production, go for iterative implementation rather than recursive.

Also, it is important to understand that it makes a huge difference when you use BSA to find a key in an array, which becomes more and more evident as data size grows. To look for a key in 1 billion integers, a simple search would take 1 billion comparisons whereas binary search will take only 32 comparisons.
If you want to learn more tricks to find mid so that case where start and end are very big numbers, read Google Reasearch on this topic.

Please share if there is anything wrong or missing. If you want to contribute to the website and share your knowledge with learners, please write to us at [email protected]