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

TC SRM443 D1 600 (BinaryFlips)

This problem can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=10387

A fairly standard problem with somewhat tricky implementation due to the problem constraints. The problem gives us "A" number of zeroes and "B" and number of ones and using a swap of exactly "K" digits in each turn, determine the minimum number of moves to get it into a state of all ones (and returning -1 if it's impossible to do so). Looking at the constraints of around 100,000 means we can't naively try all combinations. A simple approach to take is to Breadth-First searching the moves and making sure we don't re-visit already processed nodes with lower number of moves (as they will never be optimal).

We need to make several observations to help simplify the problem. As we can choose any K digits to swap over in a given turn, this means we can view the problem as a set of 0's followed by a set of 1's for simplicity. This helps us determine that the state required for the BFS is simply the number of zeroes (or ones) and not a string of disordered 0's and 1's. A further optimisation is to note that the number of zeroes can be derived from the number of ones as the total size of the string does not change. Hence the maximum state space is simply 200,000 so we are fine for memory usage. The only problem left is the transitions between states inside the inner cycle of the BFS. As the K is as large as 100,000 we will run into time limit issues if we aren't efficient in which states we check/traverse to.

This is perhaps the trickest part of the problem - the other parts are fairly standard and simple. Now we ask ourselves, "is there a way to make sure we only consider non-visited nodes?". Using a set data structure which keeps all its elements unique allows us to only traverse the unvisited states. To make another optimisation we need to ensure that we only visit the reachable unvisited states - we calculate the state range in which we can reach and do a subset traversal of the set (instead of going through the whole set and determining whether it's a valid move). To determine the range of states we need to see that if we can traverse to x-number of 1's and we can also traverse to y-number of 1's then we can also traverse to all number of 1's between x and y with the same parity. To see this, arrange a state in a sequence of 0's and 1's and take an arbitrary K (K = 4 in this case):

Move to 9 1's: 0[0000]11111 -> 0[1111]11111
Move to 7 1's: 00[0001]1111 -> 00[1110]1111
Move to 5 1's: 000[0011]111 -> 000[1100]111
Move to 3 1's: 0000[0111]11 -> 0000[1000]11
Move to 1 1's: 00000[1111]1 -> 00000[0000]1

As you can see, we can only move a specific parity (odd/even) between the minimum and maximum range. This can be seen above where we use a sliding "window" mechanism for the inversion. The parity is determined by a combination of the window size (i.e. K) and the parity of the state. To see this connection, we build an informal proof:

Let the K-sized window be denoted by W.
Let P be the parity of the state S, where S is a sequence of 0's followed by 1's.
Then we define x to be the number of 0's in S and y to be the number of 1's in S.

By definition, P = y (mod 2). Furthermore we need to define x' and y' to be the number of 0's and 1's in the window W respectively. We take x'' and y'' to be the number of 0's and 1's in the state S excluding the digits inside window W. Then it follows that:

x'' = x - x' (mod 2)
y'' = y - y' (mod 2)
x' + y' = K

Parity of the inversed window W = x' (mod 2) since it's the number of 0's in the window (as they turn into 1's after the transform which becomes the parity). We now calculate P', the parity of S after being transformed by an arbitrary K-sized window:

P' = x' (mod 2) + y'' (mod 2) (parity of the inversed window plus the region of S - W)
P' = K - y' (mod 2) + y'' (mod 2)
P' = K - y' + y'' (mod 2)
P' = K - y' + 2y' + y'' (mod 2) (add 2y' - this can be done since it doesn't alter the odd/even-ness of the equation)
P' = K + y' + y'' (mod 2)
P' = K + y (mod 2)

Therefore the next state's parity is P' = K + y (mod 2). So we only need to compute this to determine whether the parity of the next state is odd/even. So it suffices to just calculate the minimum and maximum number of 1's and then traverse based on the parity. Using all the concepts above gives us an implementation which runs at around 100ms worst case:

class BinaryFlips {
public:
 int minimalMoves(int, int, int);
};

int visited[200011];

int BinaryFlips::minimalMoves(int A, int B, int K) {
 if (A == 0) return 0;
 if (A + B < K) return -1;
 queue<int> q;
 int N = A + B;
 memset(visited,-1,sizeof(visited));
 set<int> evenVisit, oddVisit;
 for (int i = 0; i <= N; i++) {
  if (i & 1) oddVisit.insert(i);
  else evenVisit.insert(i);
 }
 if (B & 1) oddVisit.erase(oddVisit.find(B));
 else evenVisit.erase(evenVisit.erase(B));
 q.push(B);
 visited[B] = 0;
 while (!q.empty()) {
  int t = q.front(); q.pop();
  if (t == N) return visited[t];
  int numZeroes = N - t;
  int numOnes = t;
  int x = numOnes < K ? K - numOnes : numOnes - K;
  int y = numZeroes < K ? numOnes + numZeroes * 2 - K : numOnes + K;
  int s = min(x,y);
  int st = max(x,y);
  set<int>* visitSet = (t+K) & 1 ? &oddVisit : &evenVisit;
  if (visitSet->size() == 0) continue;
  set<int>::iterator it = visitSet->lower_bound(s);
  while (it != visitSet->end() && *it <= st) {
   if (visited[*it] < 0) {
    q.push(*it);
    visited[*it] = 1 + visited[t];
    set<int>::iterator itTemp = it; itTemp++;
    visitSet->erase(it);
    it = itTemp;
   } else {
    it++;
   }
  }
 }
 return -1;
}