PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Somewhat Frequent
 0/18

Binary Search on the Answer

Authors: Darren Yao, Abutalib Namazov, Andrew Wang

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

Resources
IUSACOmodule is based off this
TCsimilar material

Introduction

When we binary search on an answer, we start with a search space of size NN which we know the answer lies in. Then each iteration of the binary search cuts the search space in half, so the algorithm tests O(logN)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 xx is possible, and false otherwise. Usually, in such problems, we want to find the maximum or minimum value of xx 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 yxy \leq x.
  • If check(x) is false, then check(y) is false for all yxy \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;

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}

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}

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 yxy \geq x.
  • If check(x) is false, then check(y) is false for all yxy \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; ) {

Warning!

This code might not 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! Fixed version:

C++

1int fstTrue(function<bool(int)> f, int lo, int hi) {
2 for (hi ++; lo < hi; ) {
3 int mid = lo+hi; mid = (mid-(mid&1))/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;
6 mid = (mid-(mid&1))/2;
7 if(f(mid)) hi = mid; else lo = mid+1;
8 }
9 return lo;
10}

Example: Maximum Median

Focus Problem – read through this problem before continuing!

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

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

Solution

Problems

USACO

StatusSourceProblem NameDifficultyTagsSolution
SilverVery EasyExternal Sol
SilverEasy
SilverEasyExternal Sol
SilverEasy
SilverNormalExternal Sol
GoldHardExternal Sol
SilverVery HardExternal Sol
PlatInsane

General

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
CSESEasy
CFNormal
Show Tags

Binary Search, Prefix Sums

Check CF
CFNormalCheck CF
CFNormal
CFNormalCheck CF
CFHardCheck CF
CFHardCheck CF
Baltic OIVery Hard

Module Progress:

Give Us Feedback on Binary Search on the Answer!

PrevNext