Binary Search on the Answer
Authors: Darren Yao, Abutalib Namazov, Andrew Wang
Binary searching on arbitrary monotonic functions.
Resources | |||
---|---|---|---|
CF | |||
IUSACO | module is based off this | ||
TC | similar material |
Introduction
When we binary search on an answer, we start with a search space of size which we know the answer lies in. Then each iteration of the binary search cuts the search space in half, so the algorithm tests 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 is possible, and false
otherwise. Usually, in such problems, we want to find the maximum or minimum value of 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)
istrue
, thencheck(y)
is true for all . - If
check(x)
isfalse
, thencheck(y)
is false for all .
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++
#include <bits/stdc++.h>using namespace std;int lstTrue(function<bool(int)> f, int lo, int hi) {int res = lo-1;while (lo <= hi) {int mid = (lo+hi)/2; // find the middle of the current rangeif (f(mid)) {// if mid works, then all numbers smaller than mid also work// 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
import java.io.*;import java.util.*;public class test{public static boolean f(int x){return x*x <= 30;// function f(x) returns true or false}public static int lstTrue(int lo, int hi) {int res = lo-1;
Python
def lstTrue(f, lo, hi):""" Binary Search:param f: (lambda function) check a state:param lo: (int) lower bound:param hi: (int) upper bound:return res: (int) the maximum x such that f(x) is true"""res = lo-1while lo <= hi: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.
C++
We can shorten the function by removing res
and using a ternary if expression.
int lstTrue(function<bool(int)> f, int lo, int hi) {for (lo --; lo < hi; ) {int mid = (lo+hi+1)/2;f(mid) ? lo = mid : hi = mid-1;}return lo;}
Java
We can shorten the function by removing res
and using a ternary if expression.
public static int lstTrue(int lo, int hi) {for (lo --; lo < hi; ) {int mid = (lo+hi+1)/2;if(f(mid)) lo = mid; else hi = mid-1;}return lo;}
Python
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++
long long search(){long long pos = 0; long long max = 2E9;for(long long a = max; a >= 1; a /= 2){while(check(pos+a)) pos += a;}return pos;}
Java
static long search(){long pos = 0; long max = (long)2E9;for(long a = max; a >= 1; a /= 2){while(check(pos+a)) pos += a;}return pos;}
Python
def search():pos = 0a = mx = 2E9while a >= 1:while check(pos+a):pos += aa //= 2return 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, thencheck(y)
is true for all . - If
check(x)
is false, thencheck(y)
is false for all .
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++
#include <bits/stdc++.h>using namespace std;int fstTrue(function<bool(int)> f, int lo, int hi) {// returns smallest x in [lo,hi] that satisfies f// hi+1 if no x satisfies ffor (hi ++; lo < hi; ) {int mid = (lo+hi)/2;f(mid) ? hi = mid : lo = mid+1;}
Java
import java.io.*;import java.util.*;public class test{public static boolean f(int x){return x*x >= 30;//function f(x) returns true or false}public static int fstTrue(int lo, int hi) {for (hi ++; lo < hi; ) {
Python
def fstTrue(f, lo, hi):# returns smallest x in [lo,hi] that satisfies f# hi+1 if no x satisfies fhi+=1while lo < hi:mid = (lo+hi)//2if f(mid):hi = midelse:lo = mid + 1return loprint(fstTrue(lambda x:True, 2, 10)) # 2print(fstTrue(lambda x:x*x >= 30, 2, 10)) # 6print(fstTrue(lambda x:False, 2, 10)) # 11
Example: Maximum Median
Focus Problem – read through this problem before continuing!
Statement: Given an array of integers, where is odd, we can perform the following operation on it times: take any element of the array and increase it by . We want to make the median of the array as large as possible after operations.
Constraints: and is odd.
Solution
Mistakes to Avoid
Mistake 1 - Off By One
Consider the code from CSAcademy's Binary Search on Functions.
long long f(int x) {return (long long)x * x;}int square_root(int x) {int left = 0, right = x;while (left < right) {int middle = (left + right) / 2;if (f(middle) <= x) {left = middle;} else {right = middle - 1;}}return left;}
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++
int main() {cout << fstTrue([](int x) { return false; },-10,-10) << "\n"; // -8, should be -9cout << fstTrue([](int x) { return true; },-10,-10) << "\n"; // infinite loop}
Java
public static void main(String[] args) throws IOException{System.out.println(fstTrue(-10,-7)); // infinite loop}
This is because dividing an odd negative integer by two will round it up instead of down! New version:
C++
int fstTrue(function<bool(int)> f, int lo, int hi) {for (hi ++; lo < hi; ) {int mid = lo+(hi-lo)/2;f(mid) ? hi = mid : lo = mid+1;}return lo;}
Java
public static int fstTrue(int lo, int hi) {for (hi ++; lo < hi; ) {// returns smallest x in [lo,hi] that satisfies f// hi+1 if no x satisfies fint mid = lo+(hi-lo)/2;if(f(mid)) hi = mid; else lo = mid+1;}return lo;}
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 long
s instead of int
s.
Problems
USACO
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
Silver | Easy | |||||
Silver | Easy | |||||
Silver | Easy | |||||
Silver | Normal | |||||
Gold | Hard | External Sol | ||||
Silver | Very Hard | External Sol | ||||
Plat | Insane |
General
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!
Give Us Feedback on Binary Search on the Answer!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.