Solving Problems with Binary Search

Binary search is a lot more than just a way to find elements in a sorted array. In this tutorial, I will help you understand binary search better by going through some basic problems then applying them in technical questions asked during interviews.

Beyond arrays: the discrete binary search

Problem: Finding a value in a sorted sequence

A sequence or array is really just a function which associates integers ( that is indices of array) with the corresponding values in an array. However, there is no reason to restrict our usage of binary search to just sequences. In fact, we can use the same binary search algorithm on any monotonic function whose domain is the set of integers.
The only difference is, we will use function evaluation instead of array lookups. We will find x for which f(x) is equal to some target value.
When working with arrays, time complexity is O(log n ). But in this problem, it may change because we need to evaluate the function ( f(x) ) at every step although we will be free of any memory constraints that were present while working with arrays.

Which problem can be solved using Binary search?

If we talk in a less mathematical way, try to break the problem in a yes or no question. If the problem follows the structure below, then binary search can be used (don't worry if you don't get it clearly, example problems will make it clearer).

If you answered yes for some potential solution, x means that you’d also get a yes answer for any element after x. Similarly, if you got no, you’d get a no answer for any element before x. As a consequence, if you were to ask the question for each element in the search space (in order), you would get a series of no answers followed by a series of yes answers.

It can be easily observed that Yes and No can swap places in the description above, which means we will have a series of yeses followed by nos. In this case, yes for any x will mean that we will get yes for all elements before x and no for any x will mean that we will get no for all elements after x.

Example problems

Still confusing? Let's discuss some problems which will make the method clearer. Test your understanding of binary search by clicking the link to the problem, then once you're done answering, click the solution to the code. The explanation for each solution is provided in this tutorial.

Problem 1: ( Link to problem | Solution Code )

Explanation:

1. For the problem at hand, let us define a function F(x) such that.
   F(x) = 1 if it is possible to arrange the cows in stalls such that the distance between any two cows is at least x
   F(x) = 0 otherwisex
2. Now it is easy to see that if F(x)=0, F(y)=0 for all y>x. Thus, the problem satisfies the monotonicity condition necessary for binary search.
3. Since we have at least two cows, the best we can do is to push them towards the stalls at the end—so there is no way we can achieve this better. Hence, F(maxbarnpos-minbarnpos+1)=0.
4. Now, how do we check whether F(x)=1 for the general value of x? We can do this with a greedy algorithm: Keep placing cows at the leftmost possible stalls such that they are at least x distance away from the last cow placed. Assuming that the array pos containing positions of stalls has been sorted

int F(int x)
{
  //We can always place the first cow in the leftmost stall
  int cowsplaced=1,lastpos=pos[0];
  for(int i=1;i<N;i++)
  {
    if(pos[i]-lastpos>=x)
    {
      //We are at least x away from last placed cow
      //So we can place one here
      if(++cowsplaced==C)return 1;
      lastpos=pos[i];
    }
  }
  return 0;
}

The main function will look like:

sort(pos,pos+N);
//Invariant : F(start) is always 1, F(end) is always 0
int start=0,end=pos[N-1]-pos[0]+1,mid;
while(end-start>1)
{
  mid=(end+start)>>1;
  (F(mid)?start:end)=mid;
}
return start;

Problem 2: Asked by Google (Link to Problem | Solution Code)

Explanation:

1. Again we will design a function F(x)
   F(x) = 1 if it is possible to paint the boards in x time.
   F(x) = 0 otherwise.
2. As we can observe easily, that if boards can be painted in x time, then F(x) = 1 and also F(y) = 1 for all y >= x , Hence, we can use binary search for finding minimum x such that F(x) = 1.
3. For writing the IsPossible(x) function, we can just start allocating painters to Boards such that it's taken one painter x time, at most, to paint. If the number of allocated painters is not more than the available, then it is possible to paint the boards in x time else it is not.
4. We use binary search over the answer with limits (0, maximum time it can take), then we find if isPossible(x). If it is possible, then we search for the answer in the left half, else we go to the right half.

Problem 3: Asked by Google (Link To Problem | Solution Code)

Explanation:

1. The approach to this problem is pretty much the same as last one.
   2 pseudo-code

 simple simulation approach
   intially Sum := 0
   cnt_of_student = 0
   iterate over all books:
     If Sum + number_of_pages_in_current_book > V :
       increment cnt_of_student
       update Sum
     Else:
       update Sum
   EndLoop;
 
    fix range LOW, HIGH
    Loop until LOW < HIGH:
      find MID_point
      Is number of students required to keep max number of pages below MID < M ? 
      IF Yes:
        update HIGH
      Else
        update LOW
    EndLoop;

Wrapping up

If you find any problem that can be solved with Binary search share them on the comments section so we can add them to this list.

Related tutorials you might be interested in

• Graph Algorithms: Basic Guide for Your Next Technical Interview
• 3 Essential Algorithm Examples You Should Know
• Computer Algorithms Explained: Learning through Spotify