PrevNext
Somewhat Frequent
 0/27

Binary Search

Authors: Darren Yao, Abutalib Namazov, Andrew Wang, Qi Wang, Dustin Miao

Binary searching on arbitrary monotonic functions and built-in functions for binary search.

Introduction

Resources
CPH

code, lower_bound + upper_bound, some applications

CF EDU

videos, problems similar to those covered in this module

IUSACO

module is based off this

LC

many problems & applications

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)\mathcal{O}(\log N) values. This is efficient and much better than testing each possible value in the search space.

Binary Searching on Monotonic Functions

Let's say we have a boolean function f(x). Usually, in such problems, we want to find the maximum or minimum value of xx such that f(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.

Finding The Maximum x Such That f(x) = true

We want to construct a function lastTrue such that lastTrue(lo, hi, f) returns the last x in the range [lo,hi] such that f(x) = true. If no such x exists, then lastTrue should return lo-1.

This can be done with binary search if f(x) satisfies both of the following conditions:

  • If f(x) = true, then f(y) = true for all yxy \leq x.
  • If f(x) = false, then f(y) = false for all yxy \geq x.

For example, if f(x) is given by the following function:

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

then lastTrue(1, 8, f) = 5 and lastTrue(7, 8, f) = 6.

Implementation 1

Verify that this implementation doesn't call f on any values outside of the range [lo, hi].

C++

#include <bits/stdc++.h>
using namespace std;
int last_true(int lo, int hi, function<bool(int)> f) {
// if none of the values in the range work, return lo - 1
lo--;
while (lo < hi) {
// find the middle of the current range (rounding up)
int mid = lo + (hi - lo + 1) / 2;
if (f(mid)) {

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

Java

import java.util.function.Predicate;
public class BinarySearch {
public static void main(String[] args) {
// all numbers satisfy the condition (outputs 10)
System.out.println(lastTrue(2, 10, (x) -> true));
// outputs 5
System.out.println(lastTrue(2, 10, (x) -> x * x <= 30));

See the Java Predicate Interface if you're not familiar with the Predicate interface used.

Python

from typing import Callable
def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
"""
Binary Search
:param lo: lower bound
:param hi: upper bound
:param f: a function that returns whether a number is valid or not
:return: the maximum x such that f(x) is true

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

Implementation 2

This approach is 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. We use powers of 2, very similiar to Binary Jumping.

C++

#include <bits/stdc++.h>
using namespace std;
int last_true(int lo, int hi, function<bool(int)> f) {
lo--;
for (int dif = hi - lo; dif > 0; dif /= 2) {
while (lo + dif <= hi && f(lo + dif)) { lo += dif; }
}
return lo;
}

Java

public static int lastTrue(int lo, int hi, Predicate<Integer> f) {
lo--;
for (int dif = hi - lo; dif > 0; dif /= 2) {
while (lo + dif <= hi && f.test(lo + dif)) { lo += dif; }
}
return lo;
}

Python

from typing import Callable
def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
"""
Binary Search
:param lo: lower bound
:param hi: upper bound
:param f: a function that returns whether a number is valid or not
:return: the maximum x such that f(x) is true

Finding The Minimum x Such That f(x) = true

We want to construct a function firstTrue such that firstTrue(lo, hi, f) returns the first x in the range [lo,hi] such that f(x) = true. If no such x exists, then firstTrue should return hi+1.

Similarly to the previous part, this can be done with binary search if f(x) satisfies both of the following conditions:

  • If f(x) is true, then f(y) is true for all yxy \geq x.
  • If f(x) is false, then f(y) is false for all yxy \leq x.

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 first_true(int lo, int hi, function<bool(int)> f) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (f(mid)) {
hi = mid;
} else {

Java

import java.util.function.Predicate;
public class BinarySearch {
public static void main(String[] args) {
System.out.println(firstTrue(2, 10, (x) -> true)); // outputs 2
System.out.println(firstTrue(2, 10, (x) -> x * x >= 30)); // outputs 6
System.out.println(firstTrue(2, 10, (x) -> false)); // outputs 11
}
public static int firstTrue(int lo, int hi, Predicate<Integer> f) {

Python

from typing import Callable
def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
hi += 1
while lo < hi:
mid = (lo + hi) // 2
if f(mid):
hi = mid
else:

Example - Maximum Median

Focus Problem – try your best to solve 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.

To get the current median, we first sort the array in ascending order.

Now, notice that to increase the current value to a value, say xx. All values currently greater than or equal to the median, must remain greater than or equal to the median.

For example, say we have the sorted array [1,1,2,3,4,4,5,5,6,8,8][1,1,2,3,4,4,5,5,6,8,8]. The current median is 44, so to increase the median to 66, we have to increase the current median by 22 and we also have to increase the 55's to 66.

Following this idea, to increase the median to xx, we need to increase all values in the second half of the array to some value greater than or equal to xx.

Then, we binary search for the maximum possible median. We know that the number of operations required to raise the median to xx increases monotonically as xx increases, so we can use binary search. For a given median value xx, the number of operations required to raise the median to xx is

i=(n+1)/2nmax(0,xarr[i]).\sum_{i=(n+1)/2}^{n} \max(0, x - \texttt{arr}[i]).

If this value is less than or equal to kk, then xx can be the median, so our check function returns true. Otherwise, xx cannot be the median, so our check function returns false.

C++

#include <bits/stdc++.h>
using namespace std;
int last_true(int lo, int hi, function<bool(int)> f) {
lo--;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (f(mid)) {
lo = mid;
} else {

Here we write the check function as a lambda expression.

Java

import java.io.*;
import java.util.*;
public class MaxMed {
static int size;
static int maxOps;
static int[] arr;
public static void main(String[] args) {
Kattio io = new Kattio();

Python

from typing import Callable
def med_reachable(x: int) -> bool:
"""
Checks whether the number of given operations is sufficient
to raise the median of the array to x.
"""
ops_needed = 0
for i in range((size - 1) // 2, size):

Common Mistakes

Mistake 1 - Off By One

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

C++

long long f(int x) { return (long long)x * x; }
int sqrt(int x) {
int lo = 0;
int hi = x;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f(mid) <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}

Java

public static long f(int x) { return (long)x * x; }
public static int sqrt(int x) {
int lo = 0;
int hi = x;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f(mid) <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}

Python

def f(x: int) -> int:
return x * x
def sqrt(x: int) -> int:
lo = 0
hi = 0
while lo < hi:
mid = (lo + hi) // 2
if f(mid) <= x:
lo = mid
else:
hi = mid - 1
return lo

This results in an infinite loop if left=0 and right=1! To fix this, set middle = (left+right+1)/2 instead.

Mistake 2 - Not Accounting for Negative Bounds

Consider a slightly modified version of firstTrue:

C++

#include <functional>
using namespace std;
int first_true(int lo, int hi, function<bool(int)> f) {
hi++;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f(mid)) {
hi = mid;

Java

public static int firstTrue(int lo, int hi, Predicate<Integer> f) {
hi++;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f.test(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}

Python

from typing import Callable
def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
hi += 1
while lo < hi:
mid = (lo + hi) // 2
if f(mid):
hi = mid
else:
lo = mid + 1
return lo

This code does not necessarily work if lo is negative! Consider the following example:

C++

int main() {
// outputs -8 instead of -9
cout << first_true(-10, -10, [](int x) { return false; }) << "\n";
// causes an infinite loop
cout << first_true(-10, -10, [](int x) { return true; }) << "\n";
}

Java

public static void main(String[] args) {
// outputs -8 instead of -9
System.out.println(firstTrue(-10, -10, (x) -> false));
// causes an infinite loop
System.out.println(firstTrue(-10, -10, (x) -> true));
}

Python

# outputs -8 instead of -9
print(first_true(-10, -10, lambda x: False))
# causes an infinite loop
print(first_true(-10, -10, lambda x: True))

This is because dividing an odd negative integer by two will round it up instead of down.

C++

#include <functional>
using namespace std;
int first_true(int lo, int hi, function<bool(int)> f) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (f(mid)) {
hi = mid;

Java

public static int firstTrue(int lo, int hi, Predicate<Integer> f) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (f.test(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}

Python

from typing import Callable
def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
hi += 1
while lo < hi:
mid = lo + (hi - lo) // 2
if f(mid):
hi = mid
else:
lo = mid + 1
return lo

Mistake 3 - Integer Overflow

The first version of firstTrue won't work if hi-lo initially exceeds INT_MAX, while the second version of firstTrue won't work if lo+hi exceeds INT_MAX at any point during execution. If this is an issue, use long longs instead of ints.

Library Functions For Binary Search

C++

Resources
CPP

with examples

Example - Counting Haybales

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

As each of the points are in the range 010000000000 \ldots 1\,000\,000\,000, storing locations of haybales in a boolean array and then taking prefix sums of that would take too much time and memory.

Instead, let's place all of the locations of the haybales into a list and sort it. Now we can use binary search to count the number of cows in any range [A,B][A,B] in O(logN)\mathcal{O}(\log N) time.

With Built-in Function

C++

We can use the the built-in lower_bound and upper_bound functions.

#include <bits/stdc++.h>
using namespace std;
void setIO(string name = "") { // name is nonempty for USACO file I/O
ios_base::sync_with_stdio(0);
cin.tie(0); // see Fast Input & Output
// alternatively, cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin); // see Input & Output
freopen((name + ".out").c_str(), "w", stdout);

Java

We can use the builtin Arrays.binarySearch function.

import java.io.*;
import java.util.*;
public class Haybales {
public static void main(String[] args) throws IOException {
BufferedReader br =
new BufferedReader(new FileReader(new File("haybales.in")));
PrintWriter out = new PrintWriter("haybales.out");
StringTokenizer st = new StringTokenizer(br.readLine());

Python

We can use the builtin bisect.bisect function.

from bisect import bisect
inp = open("haybales.in", "r")
out = open("haybales.out", "w")
bale_num, query_num = map(int, inp.readline().split())
bales = sorted(list(map(int, inp.readline().split())))
for _ in range(query_num):
start, end = map(int, inp.readline().split())
print(bisect(bales, end) - bisect(bales, start - 1), file=out)

Without Using Built-in Functions

C++

#include <bits/stdc++.h>
using namespace std;
void setIO(string name = "") { // name is nonempty for USACO file I/O
ios_base::sync_with_stdio(0);
cin.tie(0); // see Fast Input & Output
// alternatively, cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin); // see Input & Output
freopen((name + ".out").c_str(), "w", stdout);

Java

import java.io.*;
import java.util.*;
public class Haybales {
static int[] bales;
public static void main(String[] args) throws IOException {
Kattio io = new Kattio("haybales");
int baleNum = io.nextInt();
int queryNum = io.nextInt();
bales = new int[baleNum];

Python

def at_most(x: int) -> int:
lo = 0
hi = len(bales)
while lo < hi:
mid = (lo + hi) // 2
if bales[mid] <= x:
lo = mid + 1
else:
hi = mid
return lo

Problems

USACO

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsBinary Search, Sorted Set
SilverEasy
Show TagsBinary Search, Sorting
SilverEasy
Show TagsBinary Search, Sorting
SilverNormal
Show TagsBinary Search, Sorting
SilverHard
Show TagsBinary Search
GoldHard
Show Tags2P, Binary Search, Greedy, Sorting
SilverVery Hard
Show TagsBinary Search, Sqrt
PlatinumInsane
Show TagsBinary Search, Sorting

General

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Search
CSESEasy
Show TagsBinary Search
CSESEasy
Show TagsBinary Search
CFEasy
Show TagsBinary Search
CCNormal
Show Tags2D Prefix Sums, Binary Search
CSESNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search, Prefix Sums
CFNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search, Greedy, Prefix Sums
CFNormal
Show TagsBinary Search, Prefix Sums
ACHard
Show TagsBinary Search, Prefix Sums, Sorting
CFHard
Show TagsBinary Search, Prefix Sums
CFHard
Show TagsBinary Search, Priority Queue
CFHard
Show TagsBinary Search
CFHard
Show TagsBinary Search
Baltic OIVery Hard
Show TagsBinary Search

Quiz

What are the worst and best case time complexities for searching for a number in a sorted array of size nn with the following code?

C++

bool binary_search(int x, std::vector<int> &a) {
int l = 0;
int r = a.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (a[m] == x) {
return true;
} else if (x > a[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
return false;
}

Java

boolean binary_search(int x, int[] a) {
int l = 0;
int r = a.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (a[m] == x) {
return true;
} else if (x > a[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
return false;
}

Python

def binary_search(x: int, a: list):
l = 0
r = len(a) - 1
while l < r:
m = (l + r) // 2
if a[m] == x:
return True
elif x > a[m]:
l = m + 1
else:
r = m - 1
return False
Question 1 of 4

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!

PrevNext