Algorithms for Problem Solving

2. Binary search

Binary search is a classic algorithm that is often used in the following situation: given a sorted list of \(n\) numbers, check if the list contains a given value in \(O(\log n)\) time. However, binary search has much wider uses in the design of algorithms, which we explore in this chapter.

There are many ways to implement binary search, and in fact, implementing the algorithm correctly can be tricky. Here is one convenient way to implement binary search:

bool binary_search(vector<int> &numbers, int value) {
    int n = numbers.size();
    int pos = -1;
    for (int step = n; step >= 1; step /= 2) {
        while (pos + step < n && numbers[pos + step] <= value) {
            pos += step;
        }
    }
    return pos >= 0 && numbers[pos] == value;
}

This function is given a sorted vector numbers and an integer value. The function returns true if value appears in numbers, and false otherwise. For example, we can use the function as follows:

vector<int> numbers = {1, 3, 3, 4, 6, 7, 7, 7};

bool check1 = binary_search(numbers, 4); // true
bool check2 = binary_search(numbers, 5); // false

We use the variable pos to find the rightmost position where numbers[pos] <= value (or \(-1\) if there is no such position). Finally, we know that value appears in numbers exactly when numbers[pos] == value.

The algorithm consists of several rounds where step denotes the increment of the variable pos. First, step is \(n\), then \(n/2\), then \(n/4\), and so on, until step is \(1\) in the last round. Using this idea, the number of increments is \(O(\log n)\).

Interestingly, there is rarely a need to implement binary search for searching for numbers in lists, because C++ and other programming languages have standard library functions for this. For example, the C++ standard library includes a function binary_search that can be used as follows:

vector<int> numbers = {1, 3, 3, 4, 6, 7, 7, 7};

bool check1 = binary_search(numbers.begin(), numbers.end(), 4); // true
bool check2 = binary_search(numbers.begin(), numbers.end(), 5); // false

In addition, we can often use other data structures, such as set, if we need to check efficiently whether an element belongs to a collection.

However, the real power of binary search is that we can use it in a more general setting, where we have a function that returns false for all parameters less than \(x\) and true for all parameters greater than or equal to \(x\). We can use binary search to efficiently find the value of \(x\). In this case, the algorithm works in \(O(\log u)\) time, where \(u\) is an upper bound for \(x\).

For example, suppose we are given a positive integer \(x\) and we want to find the minimum value of \(n\) such that \(1+2+\dots+n \ge x\). For \(x=100\), the desired answer is \(n=14\) because \(1+2+\dots+14=105\). In this case, we can create the following function:

bool valid_sum(long n, long x) {
    return n * (n + 1) / 2 >= x;
}

This function returns true exactly when \(1+2+\dots+n \ge x\). The function uses the sum formula \(1+2+\dots+n=n(n+1)/2\) to calculate the answer in \(O(1)\) time.

Then, the following function uses binary search to find the minimum value of \(n\):

long find_minimum_n(long x) {
    long n = 0;
    for (long step = x; step >= 2; step /= 2) {
        while (!valid_sum(n + step, x)) {
            n += step;
        }
    }
    return n + 1;
}

The function finds the maximum \(n\) value where valid_sum returns false. Then, we get the answer to the problem by adding one to that value. This is the minimum \(n\) value where valid_sum returns true. The function works in \(O(\log x)\) time because \(x\) is an upper bound for the answer.

The following sections show two examples of using binary search in algorithm design.

Machines and products

Suppose we have \(n\) machines and our goal is to create \(m\) products using them. For each machine, we know how many hours it takes to make one product with that machine. We can use the machines at the same time, and the task is to find the minimum number of hours needed to make all the products.

For example, consider the following situation:

In this case, the minimum number of hours required is \(24\):

We can approach this problem by looking at a reverse question: how many products can we make in \(x\) hours? This is easy to calculate: if a machine takes \(k\) hours to make one product, it can make \(\lfloor x/k \rfloor\) products in \(x\) hours. The total number of products can be found by summing up the number of products each machine can make.

In the example above, if we use \(24\) hours, we can make

\[\lfloor 24/2 \rfloor + \lfloor 24/5 \rfloor + \lfloor 24/6 \rfloor = 12+4+4=20\]

products. On the other hand, if we use \(23\) hours, we can only make

\[\lfloor 23/2 \rfloor + \lfloor 23/5 \rfloor + \lfloor 23/6 \rfloor = 11+4+3=18\]

products. Thus, \(x=24\) is the minimum number of hours where the number of products is at least \(20\).

We can now use binary search to find the answer efficiently. Suppose we have a vector machine_times that contains the number of hours each machine takes to create a product. First, let’s create a function can_make that determines if we can make goal products in hours hours using the machines:

bool can_make(vector<int> &machine_times, long goal, long hours) {
    long count = 0;
    for (auto time : machine_times) {
        count += hours / time;
    }
    return count >= goal;
}

The above function returns true if we can create all the products, and false otherwise. We can now use this function in binary search as follows:

long min_hours(vector<int> &machine_times, long goal) {
    long bound = machine_times[0] * goal;
    long answer = 0;
    for (long step = bound; step >= 1; step /= 2) {
        while (!can_make(machine_times, goal, answer + step)) {
            answer += step;
        }
    }
    return answer + 1;
}

The variable bound contains an upper bound for the number of hours. This is calculated by considering a solution where we only use the first machine. In this case the number of hours needed is machine_times[0] * total.

We use binary search to find the largest number of hours where we can’t create enough products. By adding one to this value, we get the minimum number of hours needed to create the required number of products.

The function can_make is called \(O(\log u)\) times, where \(u\) denotes the upper bound for the number of hours. Each function call takes \(O(n)\) time, where \(n\) denotes the number of machines. Thus, the total time complexity of the algorithm is \(O(n \log u)\).

Finding number pairs

As another example, suppose we are given a list of positive integers and our task is to find the maximum number of pairs, where each pair consists of two numbers such that the larger number is at least double the smaller number, and each number belongs to at most one pair.

For example, given the list \([1,2,5,2,4,7,5,4,7]\), we can create at most three pairs, such as \((1,4)\), \((2,4)\), and \((2,5)\).

We can approach the problem from a reverse viewpoint: if we have the list of numbers and a fixed number of pairs, how can we check if we can actually form the pairs?

It turns out that if we can form \(k\) pairs, one possible way to do this is to choose the \(k\) smallest numbers and the \(k\) largest numbers, and then form the pairs using the numbers in increasing order. In our previous list, the \(3\) smallest numbers are \([1,2,2]\) and the \(3\) largest numbers are \([5,7,7]\). We can form the pairs \((1,5)\), \((2,7)\), and \((2,7)\) using these numbers.

We can use binary search to find the largest possible number of pairs. First, let’s create a function can_form_pairs that checks if we can form count pairs using the given numbers. The function assumes that the list of numbers has been sorted before it is called.

bool can_form_pairs(vector<int> &numbers, int count) {
    int n = numbers.size();
    for (int pos = 0; pos < count; pos++) {
        if (numbers[pos] * 2 > numbers[n - count + pos]) {
            return false;
        }
    }
    return true;
}

We know that the answer is always at most \(\lfloor n/2 \rfloor\) because each number can appear in at most one pair. Thus, we can use binary search to find the optimal answer as follows:

int max_pairs(vector<int> &numbers) {
    sort(numbers.begin(), numbers.end());
    int answer = 0;
    int bound = numbers.size() / 2;
    for (int step = bound; step >= 1; step /= 2) {
        while (answer + step <= bound &&
               can_form_pairs(numbers, answer + step)) {
            answer += step;
        }
    }
    return answer;
}

First, the function sorts the list of numbers, and then uses binary search to find the answer. Both the sorting and binary search phases take \(O(n \log n)\) time, so the algorithm works in \(O(n \log n)\) time.

In this problem, it is also possible to find the answer more directly, without binary search, using a greedy two-pointers approach:

int max_pairs(vector<int> &numbers) {
    sort(numbers.begin(), numbers.end());
    int answer = 0;

    int n = numbers.size();
    int right = n / 2;
    for (int left = 0; left < n / 2; left++) {
        while (right < n && numbers[left] * 2 > numbers[right]) {
            right++;
        }
        if (right < n) {
            answer++;
            right++;
        }
    }
    return answer;
}

Here, left points to a number in the first half of the list, and right points to a number in the second half of the list. In each step, we create a pair that contains the smallest unused number in the first half and the smallest unused number in the second half that is large enough.

Compared to binary search, it is more difficult to explain why the above algorithm works correctly. The two-pointers phase works in \(O(n)\) time, so it is more efficient than the binary search approach. On the other hand, we have to sort the list anyway, so the total time complexity is still \(O(n \log n)\).