• ← Previous
• Next →

Used for searching a specific element in a sorted array. When you see a sorted array, the first thing that should come to your mind is binary-search.

Binary search (like Sliding Window) is an important category like the following. If you are not sure as to what should be the way to go, then think of Binary search. In fact, whenever you see a sorted array, quickly check if binary search is the way to go!

Note that in Java, we can use Collections.binarySearch() in lists and Arrays.binarySearch() on arrays. For Collections, note that the Collections.binarySearch() works ONLY on a list.

There are, in fact, two variations of binary search:

• Binary Search: In this case, if we find what we are looking for, then we return.
• Binary Range Search: In this case, if we find what we are looking for, then we continue to adjust the range till that is no longer possible.

Binary Search

Here is an implementation of Binary Search.

 int binarySearch (int[] a, int val) {
   int lo = 0, hi = a.length -1, mid;

   while (lo <= hi) { Usual loop-termination condition. Also <= is there since the array might just have a single element.
       mid = lo + (hi - lo)/2; Stops over-flow

       if (a[mid] > val) {
           hi = mid -1; Optimization; also, helps with loop-termination.
       } else if (a[mid] < val) {
           lo = mid + 1; Optimization; also, helps with loop-termination.
       } else {
           return mid;
       }
   }
   return -1;
 }

Binary Range Search

Here is an implementation of Binary Range Search. In Binary Range Search, (where ever possible, cache the possible value as ret.

 public int binaryRangeSearch(int[] a, int H) {
     int lo = 0, hi = Integer.MAX_VALUE, mid = 0;

     while (lo < hi) {
         mid = lo + (hi-lo)/2;
         if (possible(a, mid, H)) {
             hi = mid;
             ret = mid;
         } else {
             lo = mid + 1; 
         }
     }
     return ret;
 }

The possible() is a function that simply returns a Boolean saying if this range is possible or not (for a problem).

Notice that for binary search, we have the loop termination condition as (lo <= hi) but for binary range search, we have (lo < hi). For binary search, the check (lo <= hi) is there since the array might just have a single element. Note that for binary range search, we can return either lo or hi as the answer. For the while loop to break, lo must be equal to hi.

When do we need Binary Range Search?

• Two things are needed: (a) there should be a continuity/range and (b) it should be clear when we need to go left and when we need to go right.
• Since the range (answer itself) is continuous (sorted), we are doing a binary search on that.
• The goal here is usually to find one end of the range. Minimum values of that range or the Maximum value of that range.
• In problems, if the range is closed on one side and open on another side, then it makes sense to have only one value.
  • If the range is [X, INF), then the answer would seek minimum value and that would be X.
  • If the range is (-INF, X], then the answer would seek maximum value and that would be X.
  • If the range is [X1, X2], then we can return X1 as the min and X2 as the max.
• In some of these, we also use Math.ceil(). Please be aware that Math.ceil() takes a double: (int)Math.ceil((double)elem/mid);
• This may given wrong results in some cases: (int)Math.ceil(elem/mid);

When lo and hi are selected thoughtfully, you do not have to worry about mid going out of the way. You might think that why not take lo = 0 and hi = n-1. But, it is far simpler to spend some time getting the correct values for lo and hi.

Selecting correct lo and hi for binary-search problems

Find K Closest Elements

Here is an example:

Problem: https://leetcode.com/problems/find-k-closest-elements/

We can Keep lo = 0 and hi = n-K. This is because since we are selecting K elements, lo or mid can never go beyond N-K.

• ← Previous
• Next →