Binary Search

Last week, We discussed about socket programming. This week, We will discuss about a searching algorithm called binary search.

1. Seaching Problem
2. Motivation for Binary Search
3. Basic Binary Search
4. Using Loop invariants to understand it.
5. Using Binary search to find roots of certain equations.
6. Binary Search to the answer.
7. Summary and Conclusions

One of the most basic problems in computer science is to find an item in a list of items. Without any additional information, we have no choice but to search through each and every element in our list. The cost of searching in such a case is linear. If the list is searched often, then we might probably solve the problem more efficiently with a HashTable , but that would require more space.

Linear Search

---

int search(int[] a, int key) {
  if(a == null || a.length == 0) return -1;
  for(int i=0;i<a.length;i++) {

    if( a[i] == key ) {

      return i;

    }

  }

  return -1;

 }

---

Motivation For Binary Search

Binary search becomes effective when the array is sorted. In that case, just searching the array one at a time is naive. We can do better.

Suppose you are to search for a key=3 in a list from 1 to 100. Would it make sense to keep on searching If I told you to start from the item 10 ? Of course not because, after 10, all numbers after it are greater and there is no way to find the key 3. In such cases, binary search works well.

The idea is to search in the middle, check if you have gone to far and adjust the bounds. This technique is called divide and conquer. Let us look at a simple code to show it.
.

int search(int[] a, int key) {
  if(a[0] == key)  return key;
  int lo=0, hi=n-1;
  while(lo < hi) {
    int mid = lo + (hi-lo+1)/2;
      if(a[mid] > key) {
        hi = mid-1;
      }
      else {
        lo=mid;
      }

  }

  if(a[lo] < key)  return -1;
  return lo; // :)
}

How do I know If I am correct ? Well, I am using something called a loop invariant . A loop invariant is a property of a program that remains true before, during and after a program executes.

The loop invariants I maintained that enabled me to be check program correctness are

[0, lo]  Within this range, I am sure that always, a[i] <= key
[lo+1, hi]  Unexplored region, I know nothing about this range.
[hi+1,  n-1]  Within this range I am sure that  a[i] > key

So within each iteration, I compute the value of  mid if I my  mid falls within the first range, I push lo=mid , otherwise, I push  hi=mid-1. That way, i respect my invariants.

Using Binary Search to find solutions to certain monotonic functions


Write code to find the sqrt(int x). You are not allowed to use any language library functions.

To the untrained eye, It is not immediately obvious that this is solvable with binary search. Consider the function 

f(x) = sqrt(x);

if f(x) = d, then d*d = x.

Notice that if for a certain g, g*g > x, then for all t > g,

It is clear that t*t > x and so we need to adjust the range

by setting hi = mid.

Similarly, if for a certain g, g*g <= x, then for all t <= g,

t*t <= x and we set lo=mid . The function is clearly monotonic. :)

public int sqrt(int a) {
  double a1 = 1.0*a;
  double lo = 0.0;
  double hi = 1.0*a;
     
  for(int i=0;i<=1000;i++){
    double mid = (lo+hi)/2.0;
    if(mid*mid > a1)  {
      hi = mid;
    }
    else  {
      lo = mid;
    }
     
    return (int)lo;
  }

}

Notice that we ran the code for 1000 iterations, It is common to run the algorithm for a certain number of iterations for the solution to converge to the right answer. Such is common in codeforces Thanks to Mike Mirzayanov.

The last part is "Binary Search to the answer". This is kind of like a generalization to the binary search approach.

Suppose we have a range [L, R] and a predicate function f(x) that is monotonic over this range(L, R), then we can solve certain optimizations problems in R-L+1 * O(f) time if O(f) = O(n) then it is O(nlgn).

The basic binary search can be casted in terms of this where the predicate function is O(1).

Let us look at a recent problem on codeforces and how I solved it with binary search to the answer.

Problem Statement

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value ai — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has bi gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Analysis

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder. 

She can always bake 0 amounts of cake (base case).

If she can use x, then she can also use x-1. Though we don’t know if she can use x+1 and above.

How can we know if she can use x to back cake? Just do a simple linear simulation

This two statements are sufficient to solve the problem. This is the link to my solution during the contest.

In summary, you can use binary search to solve the basic searching problem provided that the list is sorted by some key. You can also extend this to find the roots of certain monotonically increasing/decreasing functions.

Finally, If you can show that a certain process or function has the monotonic property, then we can use binary search to the answer to solve certain optimization problems related to it.

Phew!!!. See you next week.