Introduction Example: Maximum Median Mistakes to Avoid Mistake 1 - Off By One Mistake 2 - Not Accounting for Negative Bounds Mistake 3 - Integer Overflow Problems USACO General Edit on Github

Somewhat Frequent

0/17

Binary Search on the Answer

Authors: Darren Yao, Abutalib Namazov, Andrew Wang

Prerequisites

An extension on binary search to search beyond an array, and rather through possible answers.

Introduction Example: Maximum Median Mistakes to Avoid Mistake 1 - Off By One Mistake 2 - Not Accounting for Negative Bounds Mistake 3 - Integer Overflow Problems USACO General

Edit on Github

Resources
CF	EDU: Binary Search - Step 2
IUSACO	12 - Binary Search	module is based off this
TC	Binary Search	similar material

Introduction

When we binary search on an answer, we start with a search space of size $N$ which we know the answer lies in. Then each iteration of the binary search cuts the search space in half, so the algorithm tests $\mathcal{O}(\log N)$ values. This is efficient and much better than testing each possible value in the search space.

Let's say we have a function check(x) that returns true if the answer of $x$ is possible, and false otherwise. Usually, in such problems, we want to find the maximum or minimum value of $x$ such that check(x) is true. Similarly to how binary search on an array only works on a sorted array, binary search on the answer only works if the answer function is monotonic, meaning that it is always non-decreasing or always non-increasing.

In particular, if we want to find the maximum x such that check(x) is true, then we can binary search if check(x) satisfies both of the following conditions:

If check(x) is true, then check(y) is true for all $y \leq x$ .
If check(x) is false, then check(y) is false for all $y \geq x$ .

For example, the last point at which the condition below is satisfied is 5.

check(1) = true
check(2) = true
check(3) = true
check(4) = true
check(5) = true
check(6) = false
check(7) = false
check(8) = false

Below, we present several algorithms for binary search, which search for the maximum x such that f(x) is true.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int lstTrue(function<bool(int)> f, int lo, int hi) {
5    int res = lo-1;
6    while (lo <= hi) {
7        int mid = (lo+hi)/2; // find the middle of the current range
8        if (f(mid)) {
9            // if mid works, then all numbers smaller than mid also work
10            // so we only care about the part after mid

See Lambda Expressions if you're not familiar with the syntax used in the main function.

Java

1import java.io.*; 
2import java.util.*; 
3
4public class test{
5    public static boolean f(int x){
6        return x*x <= 30;
7        // function f(x) returns true or false
8    }
9    public static int lstTrue(int lo, int hi) {
10        int res = lo-1;

Python

1def lstTrue(f, lo, hi):
2    """ Binary Search
3    :param f: (lambda function) check a state
4    :param lo: (int) lower bound
5    :param hi: (int) upper bound
6    :return res: (int) the maximum x such that f(x) is true
7    """
8    res = lo-1
9    while lo <= hi:
10        mid = (lo+hi)//2 # find the middle of the current range

See Lambda Expressions if you're not familiar with the syntax used in the program.

We can shorten the function by removing res and using a ternary if expression.

C++

1int lstTrue(function<bool(int)> f, int lo, int hi) {
2    for (lo --; lo < hi; ) {
3        int mid = (lo+hi+1)/2;
4        f(mid) ? lo = mid : hi = mid-1;
5    }
6    return lo;
7}

Java

1public static int lstTrue(int lo, int hi) {
2    for (lo --; lo < hi; ) {
3        int mid = (lo+hi+1)/2;
4        if(f(mid)) lo = mid; else hi = mid-1;
5    }
6    return lo;
7}

Python

Note: it is NOT recommended to use tenary expression in the python implementation of binary search because python tenary expression does not accept statements.

Python ternary expression

There is also another approach to binary searching based on interval jumping. Essentially, we start from the beginning of the array, make jumps, and reduce the jump length as we get closer to the target element.

C++

1long long search(){
2    long long pos = 0; long long max = 2E9;
3    for(long long a = max; a >= 1; a /= 2){
4        while(check(pos+a)) pos += a;
5    }
6    return pos;
7}

Java

1static long search(){
2    long pos = 0; long max = (long)2E9;
3    for(long a = max; a >= 1; a /= 2){
4        while(check(pos+a)) pos += a;
5    }
6    return pos;
7}

Python

1def search():
2    pos = 0
3    a = mx = 2E9
4    while a >= 1:
5        while check(pos+a):
6            pos += a
7        a //= 2
8    return pos

If instead we're looking for the minimum x that satisfies some condition, then we can binary search if check(x) satisfies both of the following conditions:

If check(x) is true, then check(y) is true for all $y \geq x$ .
If check(x) is false, then check(y) is false for all $y \leq x$ .

The binary search function for this is very similar. We will need to do the same thing, but when the condition is satisfied, we will cut the right part, and when it's not, the left part will be cut.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int fstTrue(function<bool(int)> f, int lo, int hi) {
5    // returns smallest x in [lo,hi] that satisfies f
6    // hi+1 if no x satisfies f
7    for (hi ++; lo < hi; ) {
8        int mid = (lo+hi)/2;
9        f(mid) ? hi = mid : lo = mid+1;
10    }

Java

1import java.io.*; 
2import java.util.*; 
3
4public class test{
5    public static boolean f(int x){
6        return x*x >= 30;
7        //function f(x) returns true or false
8    }
9    public static int fstTrue(int lo, int hi) {
10        for (hi ++; lo < hi; ) {

Python

1def fstTrue(f, lo, hi):
2    # returns smallest x in [lo,hi] that satisfies f
3    # hi+1 if no x satisfies f
4    hi+=1
5    while lo < hi:
6        mid = (lo+hi)//2 
7        if f(mid): 
8            hi = mid
9        else:
10            lo = mid + 1

Example: Maximum Median

Div 2 C - Maximum Median

CF - Easy

Focus Problem – read through this problem before continuing!

Statement: Given an array $\texttt{arr}$ of $n$ integers, where $n$ is odd, we can perform the following operation on it $k$ times: take any element of the array and increase it by $1$ . We want to make the median of the array as large as possible after $k$ operations.

Constraints: $1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$ and $n$ is odd.

Solution

Mistakes to Avoid

Mistake 1 - Off By One

Consider the code from CSAcademy's Binary Search on Functions.

1long long f(int x) {
2    return (long long)x * x;
3}
4int square_root(int x) {
5    int left = 0, right = x;
6    while (left < right) {
7        int middle = (left + right) / 2;
8        if (f(middle) <= x) {
9            left = middle;
10        } else {

This loops infinitely if left=0 and right=1! To fix this, set middle = (left+right+1)/2 instead.

Mistake 2 - Not Accounting for Negative Bounds

The fstTrue code given above does not necessarily work if lo is negative! Consider the following example:

C++

1int main() {
2    cout << fstTrue([](int x) { return false; },-10,-10) << "\n"; // -8, should be -9
3    cout << fstTrue([](int x) { return true; },-10,-10) << "\n"; // infinite loop
4}

Java

1public static void main(String[] args) throws IOException
2{
3     System.out.println(fstTrue(-10,-7)); // infinite loop
4}

This is because dividing an odd negative integer by two will round it up instead of down! New version:

C++

1int fstTrue(function<bool(int)> f, int lo, int hi) {
2    for (hi ++; lo < hi; ) {
3        int mid = lo+(hi-lo)/2;
4        f(mid) ? hi = mid : lo = mid+1;
5    }
6    return lo;
7}

Java

1public static int fstTrue(int lo, int hi) {
2   for (hi ++; lo < hi; ) {
3      // returns smallest x in [lo,hi] that satisfies f
4      // hi+1 if no x satisfies f
5      int mid = lo+(hi-lo)/2;
6      if(f(mid)) hi = mid; else lo = mid+1;
7   }
8   return lo;
9}

Mistake 3 - Integer Overflow

The first version of fstTrue won't work if lo+hi exceeds INT_MAX at any point during execution, while the second version of fstTrue won't work if hi-lo initially exceeds INT_MAX. In this case, make the bounds long longs instead of ints.

Problems

USACO

Source	Problem Name	Difficulty	Solution
Silver	Cow Dance Show	Easy	Internal Sol
Silver	Convention	Easy	External Sol
Silver	Angry Cows	Easy	Internal Sol
Silver	Social Distancing	Normal	External Sol
Gold	Angry Cows	Hard	External Sol
Silver	Loan Repayment	Very Hard	External Sol
Plat	Load Balancing	Insane	Internal Sol

General

Source	Problem Name	Difficulty	Tags	Solution
CSES	Factory Machines	Easy		Internal Sol
CSES	Array Division	Easy		Internal Sol
CF	Edu C: Magic Ship	Normal	Show Tags Binary Search, Prefix Sums	Check CF
CF	The Meeting Place Cannot Be Changed	Normal		Check CF
CF	Preparing for Merge Sort	Normal		Internal Sol
CF	Office Keys	Normal		Check CF
CF	Packmen	Hard		Check CF
CF	Level Generation	Hard		Check CF
Baltic OI	Mobile	Very Hard		Internal Sol

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum

Table of Contents

Binary Search on the Answer

Prerequisites

Table of Contents

Introduction

Example: Maximum Median

Mistakes to Avoid

Mistake 1 - Off By One

Mistake 2 - Not Accounting for Negative Bounds

Mistake 3 - Integer Overflow

Problems

USACO

General

Module Progress:

Join the USACO Forum!

Give Us Feedback on Binary Search on the Answer!

Table of Contents

Binary Search on the Answer

Prerequisites

Table of Contents

Introduction

Example: Maximum Median

Mistakes to Avoid

Mistake 1 - Off By One

Mistake 2 - Not Accounting for Negative Bounds

Mistake 3 - Integer Overflow

Problems

USACO

General

Module Progress:Not Started

Join the USACO Forum!

Give Us Feedback on Binary Search on the Answer!

Module Progress: