Binary search algorithm

Binary search algorithm

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

Let’s understand what is 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, first question is what should be output if key does not exist in array? What happens if there are duplicate integers in array, which index should be returned? May be 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 array and compare them with key, once key matches any element, we return the index saying key was found at that index. Simple isn’t it? How many comparisons you have to make in worst case scenario? Yes, it will be equal to number of elements in array to be searched. In big O notation, worst complexity of 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 array.

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

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

In brute force solution, we started with first element and went all the way to 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 array based on condition described. Optimum solution would be to start from the 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 left part of mid or right part of 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 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 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.

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.

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

Now that we have learned algorithm and solved couple of examples, it’s time to implement 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 element at mid is not equal to key
            what is relationsip 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 element at mid is not equal to key
            what is relationsip 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 complexity of 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 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 array, which becomes more and more evident as data size grows. To look for a key in 1 billion integers, simple search would take 1 billion comparisons where as 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 website and share your knowledge with learners, please write to us at communications@algorithmsandme.com.