Binary Search Algorithm

We all know that binary search can be used to efficiently find whether or not a specific element is in a sorted array/sequence. The time complexity of binary search is O(log n) which means it's very fast even for extremely large ranges. However in a generalised sense, we can apply binary search to any monotonically increasing sequence or abstract function.

Let a function f(x) return true or false according to a specific criteria. If for all values of f(x) <= f(x+1) then we can use binary search to find the smallest spot in which the value changes from false to true in O(log n) time. In relation to searching for a specific element in a sorted sequence - we can define f(x,s) as follows:

f(x,s) = false if x is smaller than s (the term we want to search for)
f(x,s) = true otherwise

Then if we attempt to map out the function for all values of x we yield a sequence like:

f(1,6) f(2,6) f(3,6) f(4,6) f(5,6) f(6,6) ...
false, false, false, false, false, true, true, true, ...

Algorithmically, for f(x,s) being false we move up the lower bound to the middle (low + high / 2). Conversely, for f(x,s) being true we move down the lower bound to the middle. Hence we can make a generic binary search function like so:

while (hi > lo + 1) {
   long long mid = (lo + hi) / 2;
   if (func(mid)) {
      hi = mid;
   } else {
      lo = mid;
   }
}

output hi as the answer

As a concrete example, we will solve a problem using this generalised version of binary search:

Problem: Mortgage
Source: Topcoder SRM 189 D2 1000
URL: http://www.topcoder.com/stat?c=problem_statement&pm=2427&rd=4765

This problem asks us to find the minimum monthly payment we need to make to fulfill our loan without exceeding the number of terms we are allowed to repay in. The first thing to look for in a binary search problem is whether or not the monotonicity holds. In this case, if we can pay the loan amount using $x under n terms then we can also do the same for any loan amount greater than $x. We begin by defining our binary search boolean function:

Let F(x) = false if we can't pay the loan amount using $x under n terms
Let F(x) = true otherwise

Then we can see the monotonic sequence as:

false, false, false, ..., false, true, ... true

Our task is then to find the x value in which the value of F(x) changes from false to true. We can use a sequential search for this by iteratively going from 1 to x. However given the fact that the worst case scenario for this problem is at least 2 billion - this would surely TLE. Therefore, we turn to binary search in which we can solve the problem with a handful of iterations.

Using our general binary search template given above, we can easily come up with an efficient implementation. We also note the need for 64-bit integers due to overflow problems. Another minor note is that we need to terminate if what we pay is not enough to cover the interest - as in these cases the number of terms required to pay back is infinite (and hence false). The rounding can simply be done by adding 11999 before we divide - this will ensure that we always round up to the next integer as require by the problem.

The implementation is below:

class Mortgage {
public:
  int monthlyPayment(int, int, int);
};

bool calcTime(long long loan, int interest, long long payment, int terms) {
  long long current = loan;
  while (current > 0 && terms > 0) {
    current -= payment;
    if (current <= 0) return true;
    long long d = current + (current * interest + 11999)/12000;
    if (d > current + payment) return false;
    current = d;
    terms--;
  }
  return false;
}

int Mortgage::monthlyPayment(int loan, int interest, int term) {
  long long lo = 1, hi = 2000000000;
  while (hi > lo + 1) {
    long long mid = (lo + hi) / 2;
    if (calcTime(loan,interest,mid,term*12)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

On a side note, the binary search function can also be applied to real (double) numbers. However, in this case due to rounding and machine precision problems it becomes somewhat risky to use straight arithmetic to determine the stopping case. In such cases, it is simpler and less risky to have a maximum number of iteration the loop can run for. Although this is a bit dodgy, given a suitable amount of iterations the answer will be precise as the binary search algorithm converges very fast. A template of such a binary search is given below:

#define MAX_ITER 1000
#define EPS 1e-09

while (fabs(hi-lo) > EPS && iter < MAX_ITER) {
   double mid = (lo + hi) / 2;
   if (func(mid)) {
      hi = mid;
   } else {
      lo = mid;
   }
   iter++;
}
output hi as the answer