Keep an eye on the binary search algorithm

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.

Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

To understand the problem, let’s understand what is a sorted array, and then what is sorted rotated array?

An array is called sorted where for all i and j such that i < j, A[i] <= A[j].
A rotation happens when the last element of an array is pushed at the start and all elements of array move right by one position. This is called as rotation by 1. If the new last element is also pushed to start again, all elements are moved to the right, it’s a rotation by 2, and so on.

minimum in rotated sorted array

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

Minimum in sorted rotated array and binary search algorithm

As always, first, come up with a brute force solution without worrying about any optimizations as of now. The simplest way would be to scan through the array and keep track of the minimum. The complexity of this method is O(n).

In the brute force solution, we did not use the fact that the array is sorted and then rotated. Let’s forget about rotation and concentrate only on the sorted part.

What is the minimum element in a sorted array? Obviously, it is the first element of the array. We see that all the elements on the right side of the minimum elements are greater than the minimum.

What will happen if start rotating array now, is the condition that all the elements on the right of the minimum element are greater than it still holds? Yes, it does. Either there will be no element on the right side of minimum or the will be definitely greater than it. So it is obvious, that the first element in the sorted part of the array is a candidate for the minimum element in a sorted rotated array, rest all can be discard.

What if we start with the middle element. How do I know that if array on the right side of it is sorted or not? What information comparison between the middle and end gives us?

If middle element is less than the last element, the array is sorted from index mid to end, in this case, we have to look for minimum on the left part including the mid
minimum in sorted rotated array

If the middle element will be greater than the last element, array on the right side is not sorted, there must be someplace in this right part, where the sorted array start, hence minimum element should be in the right part of the array.

find minimum in rotated array

When should we stop? Well, what is the minimum of an array with only one element? The element itself. We will also stop when there is only 1 element left.

Algorithm to find minimum in sorted rotated array

  1. Find mid = start + (end- start) /2
  2. See if mid is part of sorted array or not, check A[mid] < A[end]
  3. If yes, minimum should be on the left part
  4. If no, minimum should be on the right part

Minimum in sorted rotated array implementation

class Solution {
    public int findMin(int[] nums) {
        
        int start = 0;
        int end = nums.length-1; //O(1)
        int mid;
        
        while(start < end){
            mid = start + ((end - start)/2);
        
            if(nums[mid]<nums[end]){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        
        return nums[start];
    }
}

The complexity of the algorithm to find minimum in a sorted rotated array is O(logn) because of binary search algorithm.

This problem is asked in many variations like find pivot in a sorted rotated array or find the number of rotations.

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.

Find element in sorted rotated array

Find element in sorted rotated array

To understand how to find element in sorted rotated array, we must understand first, what is a sorted rotated array? An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements on array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again all elements are moved to right again, it’s rotation by 2 and so on.

Find element in sorted rotated array
Sorted array
Sorted rotated array

Question which is very commonly asked in Amazon and Microsoft initial hacker round interviews or telephonic interviews : Given a sorted rotated array, find position of an element in that array. For example:

A = [2,3,4,1] Key = 4, Returns 2 which is position of 4 in array

A = [4,5,6,1,2,3] Key = 4 returns 0

Find element in sorted rotated array : Thought process

Before starting with any solution, it’s good to ask some standard questions about an array problem, for example, if duplicate elements are allowed or if negative numbers are allowed in array? It may or may not change the solution, however, it gives an impression that you are concerned about input range and type.

First thing to do in interview is come up with brute force solution, why? There are two reasons : first, it gives you confidence that you have something solved, it may not be optimal way but still you have something. Second, now that you have something written, you can start looking where it takes most of time or space and attack the problem there. It also, helps to identify what properties you are not using which are part of the problem and help your solution.

First thing first, what will be the brute force solution? Simple solution will be to scan through the array and find the key. This algorithm will have O(N) time complexity.

There is no fun in finding an element in sorted array in O(N) 🙂 It would have been the same even if array was not sorted. However, we already know that our array is sorted. It’s also rotated, but let’s forget about that for now. What do we do when we have to find an element in sorted array? Correct, we use binary search.

We split the array in middle and check if element at middle index is the key we are looking for? If yes, bingo! we are done.

If not, if A[mid] is less that or greater than key. If it is less, search in right subarray, and it is greater, search in left subarray. Any which way, our input array is reduced to half. Complexity of binary search algorithm is log (N). We are getting somewhere 🙂

Sorted rotated array

However, our input array in not a plain sorted array, it is rotated too. How does things change with that. First, comparing just middle index and discarding one half of array will not work. Still let’s split the array at middle and see what extra conditions come up?
If A[mid] is equal to key, return middle index.
There are two broad possibilities of rotation of array, either it is rotated more than half of elements or less than half of elements. Can you come up with examples and see how array looks like in both the cases?

If array is rotated by more than half of elements of array, elements from start to mid index will be a sorted.

If array is rotated by less than half of elements of array, elements from mid to end will be sorted.

Next question, how do you identify the case, where array is rotated by more or less than half of elements? Look at examples you come up with and see if there is some condition?

Yes, the condition is that if A[start] < A[mid], array is rotated more than half and if A[start] > A[mid], it is rotated by less than half elements.

Now, that we know, which part of array is sorted and which is not. Can we use that to our advantage?

Case 1 : When array from start to mid is sorted. We will check if key > A[start] and key < A[mid]. If that’s the case, search for key in A[start..mid]. Since, A[start..mid] is sorted, problem reduces to plain binary search. What if key is outside of start and middle bounds, then discard A[start..mid] and look for element in right subarray. Since, A[mid+1..right] is still a sorted rotated array, we follow the same process as we did for the original array.

Case 2 : When array from mid to end is sorted. We will check if key >A[mid] and key < A[end]. If that’s the case, search for key in A[mid+1..end]. Since, A[mid+1..end] is sorted, problem reduces to plain binary search. What if key is outside of mid and end bounds, then discard A[mid..end] and search for element in left subarray. Since, A[start..mid-1] is still a sorted rotated array, we follow the same process as we did for the original array.

Let’s take an example and go through the entire flow and then write concrete algorithm to find element in sorted rotated array.

Below is sorted rotated array given and key to be searched is 6.

We know, A[start] > A[mid], hence check if searched key fall under range A[mid+1..end]. In this case, it does. Hence, we discard A[start..mid].

At this point, we have to options:  either fallback to traditional binary search algorithm or continue with same approach of discarding based on whether key falls in range of sorted array. Both methods work. Let’s continue with same method.

Again find middle of array from middle +1 to end.

A[mid] is still not equal to key. However, A[start] < A[mid]; hence, array from A[start] to A[middle] is sorted. See if our key falls between A[start] and A[mid]? Yes, hence, we discard the right sub array A[mid..End]

Find the middle of remaining array, which is from start to old middle – 1.

Is A[mid] equal to key? No. Since, A[start] is not less than A[mid], see if key falls under A[mid+1..end], it does, hence discard the left subarray.

Now, new middle is equal to key are searching for. Hence return the index.

Similarly, we can find 11 in this array. Can you draw the execution flow that search?

Algorithm to find element in sorted rotated array

  1. Find mid =  (start + end)/ 2
  2. If A[mid] == key; return mid
  3. Else, if A[start] < A[end]
    • We know, left subarray is already sorted.
    • If A[start] < key and A[mid] > key :
      • discard A[mid..end]
      • Continue with new subarray with start and end = mid – 1
    • Else:
      • discard A[start..mid]
      • Continue with new subarray with start = mid + 1 and end
  4. Else
    • We know, right subarray is sorted.
    • If A[mid] < key and A[end] > key :
      • discard A[start..mid]
      • Continue with new subarray with start  = mid + 1 and end
    • Else:
      • discard A[start..mid]
      • Continue with new subarray with start and end = mid – 1

Find element in sorted rotated array : Implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

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

        if(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
                     */
                    return findElementRecursive(input, start, mid - 1, key);
                }else{
                    /*
                    Key lies in right subarray
                     */
                    return findElementRecursive(input, mid + 1, end, key);
                }
            }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
                     */
                    return findElementRecursive(input, mid + 1 , end, key);
                }else{
                    /*
                    Key lies in left subarray
                     */
                    return findElementRecursive(input, start, mid - 1, key);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,5,6,7,8,9};

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

    }
}

Iterative implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

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

        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;
    }

    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,5,6,7,8,9};

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

    }
}

Complexity of above recursive and iterative algorithm to find an element in a rotated sorted array is O(log n). Recursive implementation has implicit space complexity of O(log n)

What did we learn today? We learned that it’s always better to come up with non-optimized solution first and then try to improve it. Also helps to correlate problem with similar and simpler problem like we understood first what is best way to find an element in sorted array and then extrapolated the solution with additional conditions for our problem.

I hope that this post helped you with this problem and many more similar problems you will see in interviews.

Please share if you have some questions or suggestions. Also, if you want to contribute on this learning process of others, please contact us.