Guide to Competitive Programming

Binary search is an O(log n) time algorithm that can be used, for example, to efficiently check whether a sorted array contains a given element. In this section, we first focus on the implementation of binary search, and after that, we will see how binary search can be used to find optimal solutions for problems.

Binary Search

Implementing the Search:

Suppose that we are given a sorted array of n elements and we want to check if the array contains an element with a target value x. Next we discuss two ways to implement a binary search algorithm for this problem.

First Method The most common way to implement binary search resembles looking for aword in a dictionary.3 The search maintains an active subarray in the array, which initially contains all array elements. Then, a number of steps are performed, each of which halves the search range. At each step, the search checks the middle element of the active subarray. If the middle element has the target value, the search terminates.

Otherwise, the search recursively continues to the left or right half of the subarray, depending on the value of the middle element. For example, Fig. 4.14 shows how an element with value 9 is found in the array.

The search can be implemented as follows:

int a = 0, b = n-1;
while (a <= b) {
int k = (a+b)/2;
if (array[k] == x) {
// x found at index k
}
if (array[k] < x) a = k+1;
else b = k-1;
}

In this implementation, the range of the active subarray is a . . . b, and the initial range is 0 . . . n − 1. The algorithm halves the size of the subarray at each step, so the time complexity is O(log n).

Some people, including the author of this book, still use printed dictionaries. Another example is finding a phone number in a printed phone book, which is even more obsolete.

Implementing the Search

Second Method Another way to implement binary search is to go through the array from left to right making jumps. The initial jump length is n/2, and the jump length is halved on each round: first n/4, then n/8, then n/16, etc., until finally the length is 1. On each round, we make jumps until we would end up outside the array or in an element whose value exceeds the target value. After the jumps, either the desired element has been found or we know that it does not appear in the array. Illustrates the technique in our example scenario.

The following code implements the search:

int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
// x found at index k
}

During the search, the variable b contains the current jump length. The time complexity of the algorithm is O(log n), because the code in the while loop is performed at most twice for each jump length.

Finding Optimal Solutions:

Suppose that we are solving a problem and have a function valid(x) that returns true if x is a valid solution and false otherwise. In addition, we know that valid(x) is false when x < k and true when x ≥ k. In this situation, we can use binary search to efficiently find the value of k.

The idea is to binary search for the largest value of x for which valid(x) is false. Thus, the next value k = x + 1 is the smallest possible value for which valid(k) is true. The search can be implemented as follows:

Finding Optimal Solutions

int x = -1;
for (int b = z; b >= 1; b /= 2) {
while (!valid(x+b)) x += b;
}
int k = x+1;

The initial jump length z has to be an upper bound for the answer, i.e., any value for which we surely know that valid(z) is true. The algorithm calls the function valid O(log z) times, so the running time depends on the function valid. For example, if the function works in O(n) time, the running time is O(n log z).

Example Consider a problem where our task is to process k jobs using n machines.

Each machine i is assigned an integer pi : the time to process a single job. What is the minimum time to process all the jobs?
For example, suppose that k = 8, n = 3 and the processing times are p1 = 2, p2 = 3, and p3 = 7. In this case, the minimum total processing time is 9, by following the schedule.

Let valid(x) be a function that finds out whether it is possible to process all the jobs using at most x units of time. In our example scenario, clearly valid(9) is true, because we can followthe schedule. On the other hand, valid(8) must be false, because the minimum processing time is 9.

Calculating the value of valid(x) is easy, because each machine i can process at most x/pi  jobs in x units of time. Thus, if the sum of all x/pi  values is k or more, x is a valid solution. Then, we can use binary search to find the minimum value of x for which valid(x) is true.

How efficient is the resulting algorithm? The function valid takes O(n) time, so the algorithm works in O(n log z) time, where z is an upper bound for the answer.

One possible value for z is kp1 which corresponds to a solution where only the first machine is used to process all the jobs. This is surely a valid upper bound.