Keep an eye on the binary search algorithm

Tags: , ,

What is binary search algorithm

A classic example of the application of the binary search algorithm is searching for a word in a dictionary, or when you open a page in a book. The process you follow depends on two things: first, you know that words in the dictionary or pages in the book are in sorted order; second, you know what is the lower bound and upper bound of search space? The word you are looking for should start with A to Z or page you are looking for should be between the first page and the last page of the book.

If it is a sorted range of items and you know the upper and lower bound of your result, think binary search algorithm

Most important fact to know about binary search is that it reduces search complexity from linear O(n) to logarithmic O(log n).

A typical iterative implementation of the binary search algorithm looks like below. To understand more how it exactly works in details, follow this post on it.

    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 the 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;
    }
How can you test your binary search implementation? Always dry run your code against an array of size 1 and 2. See if your code works for these cases properly? If it does, it will work for the rest of the cases as well.

A log of candidates get confused when to return from the while loop, should it be start < end or should it be start <= end Here is the rule of thumb for this:

If you are returning within the while loop (like in above case), use start<=end, if you are not returning from while loop, use start < end (like first occurrence and last occurrences )

Whenever you have identified a problem to be a binary search problem, just go ahead and write down the template code above first and then do the modifications. Another thing you should consider is should mid be included in subproblem or should it be discarded. In the implementation of plain binary search, if A[mid] is not equal to key, mid is no more a candidate, whereas in first instance problem, mid remains candidate in left part of the search.

1. Last occurrence of an element in a sorted array

    public int findLastOccurrence (int[] a, int key) {
        return findLastOccurrence(a, 0, a.length-1, key);
    }
    private int findLastOccurrence (int[] a, int start, 
                                 int end, int key){
      /*We do not return from the while loop
       start is less than end */
        while(start < end){
            /* Notice that we have + 1 to move start
                 in case there are only two elements left
             */

            int mid = start + ((end - start) +1) / 2;

            if(a[mid] <= key){
                start = mid;
            }
            else{
                end= mid-1;
            }
        }
        return (a[end] == key) ? end : -1;
    }

2. Find the ceiling of a number in a sorted array

private int findCeiling (int[] a, int start,
                             int end, int key){

      /*We do not return from the while loop
       start is less than end */
        while(start < end){
            int mid = start + ((end - start)) / 2;

            if(a[mid] < key){
                start = mid + 1;
            }
            else{
                end= mid;
            }
        }

        return start;
    }

Binary search and sorted rotated array

One pattern of the binary search algorithm that is usually asked in interviews is sorted rotated array. Given a sorted rotated array, find the pivot or find the minimum in that array or find an element in it.

Key to apply binary search on a sorted rotated array is that if you split it in the middle, at least one part will be sorted.

Compare the middle element with the end of the array and you know which part is sorted. If A[mid] < A[end] then right part is sorted and if A[mid] > A[end] then left part is sorted. Based on this information, we can check if the key falls in the sorted part if not, the look in the unsorted part.

Find an element in sorted rotated array

       public static int findElementIteratve(int[] input, int start, 
                                      int end, int key) {

       //Returning within while loop, so start<=end
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (input[mid] == key) return mid;

            else if (input[start] <= input[mid]) {
                /*Left sub array is sorted, check if
                key is with A[start] and A[mid] */
                if (input[start] <= key && input[mid] > key) {
                    /*
                      Key lies with left sorted part of array
                     */
                    end = mid - 1;
                } else {
                    /*
                    Key lies in right subarray
                     */
                    start  = mid + 1;
                }
            } else {
                /*
                 In this case, right subarray is already sorted and
                 check if key falls in range A[mid+1] and A[end]
                 */
                if (input[mid + 1] <= key && input[end] > key) {
                    /*
                      Key lies with right sorted part of array
                     */
                    start = mid + 1;
                } else {
                    /*
                    Key lies in left subarray
                     */
                    end  = mid - 1;
                }
            }
        }
        return -1;
    }

Minimum in a sorted rotated array

    public int findMinimum (int[] a) {
        return findMinimum(a, 0, a.length-1);
    }
    
    private int findMinimum (int[] a, int start,
                             int end){
        while (start < end) {
            int mid = start + (end - start) / 2;

            /* Check if left part of the array is sorted
             or the right part */
            if (a[mid] < a[end]) {
                /*If left part is sorted,
                  then minimum cannot be on
                  the right side of mid,
                  but mid still can be.
                 */
                end  = mid;
            } else {
                start  = mid+1;
            }
        }
        return start;
    }

Binary search and invisible input range

There are some problems which do not appear to be a binary search problem at first. For example, ship capacity problem on leetcode. At first glance, it does not appear to be a binary search problem. Where is the input we will search on? That's where we have to remember that to apply a binary search, we actually do not need an input set, all we need is lower and upper bound.
How can we find the lower and upper bound of ship capacity?

To find these bounds, try to vary the constraint to extremes. In the example of ship capacity, try to put the number of days constraints to an extreme. What if we had an infinite number of days to ship the cargo?

In that case, we will need a ship that has at least capacity greater than equal to the heaviest weight cargo, as no matter how many days, we cannot move the cargo.

Again, what if I had only 1 day to ship the whole cargo? In that case, we need a ship that can take all the weights in 1 day, so ship capacity should be sum of all the weights.

Now, we know the lower and upper bound of the ship, all we have to adjust the capacity and see if we can ship cargo in D days? Start with mid, see if we can. If yes, then try a smaller capacity. If not, then try greater capacity. All we are doing is find the first capacity between lower and upper bounds. It seems like the first occurrence problem now.

    public int shipWithinDays(int[] weights, int D) {
        
        int upperLimit = 0;
        int lowerLimit = 0;
        
        for(int i = 0; i<weights.length; i++){
            upperLimit+= weights[i];
        }
        //Not returning from while loop :)
        while(lowerLimit < upperLimit){
            int shipCapacity = lowerLimit + (upperLimit - lowerLimit)/2;
            
            if(isItPossible(D, shipCapacity, weights)){
                upperLimit = shipCapacity;
            }
            else{
                lowerLimit = shipCapacity + 1;
            }
        }
        
        return lowerLimit;
        
    }
    
    private boolean isItPossible(int D, int shipCapacity, int[] weights){
        
        int currentLoad = 0;
        int days = 1;
        int i = 0;
        
        while(i<weights.length){
            if(weights[i] > shipCapacity) return false;
            
            currentLoad+= weights[i];
            if(currentLoad == shipCapacity){
                days++; i++;
                currentLoad = 0;
            }
            else if(currentLoad > shipCapacity){
                days++;
                currentLoad = 0;
            }
            else{
                i++;
            }
        }
        
        return days <= D;
    }

If you are looking for more problems on this concept, follow number of pages to read problem

Please share if there is any issue or mistake in the post. We provide coaching to prepare you for an interview, we explain concepts, problems, tips, and tricks to master in an interview. If you are interested in such coaching, please book a session with us.