Somewhat Frequent
0/25

# Binary Search

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

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

## Introduction

Resources
CPH

code, lower_bound + upper_bound, some applications

CF

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 $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.

## 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 $x$ 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 $y \leq x$.
• If f(x) = false, then f(y) = false for all $y \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 lastTrue(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		System.out.println(lastTrue(2, 10, (x) -> true));  // outputs 10				System.out.println(lastTrue(2, 10, (x) -> x * x <= 30));  // outputs 5				// no numbers satisfy the condition

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

Python

from typing import Callable

def lastTrue(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 lastTrue(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 lastTrue(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 $y \geq x$.
• If f(x) is false, then f(y) is false for all $y \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 firstTrue(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 firstTrue(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 – 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

## 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) {

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) {

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 firstTrue(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 firstTrue(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 << firstTrue(-10, -10, [] (int x) { return false; }) << "\n";		// causes an infinite loop	cout << firstTrue(-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 -9print(firstTrue(-10, -10, lambda x: False))
# causes an infinite loopprint(firstTrue(-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 firstTrue(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 firstTrue(lo: int, hi: NotImplemented, 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 – read through this problem before continuing!

View Internal Solution

As each of the points are in the range $0 \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]$ in $\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());
int baleNum = Integer.parseInt(st.nextToken());

Python

We can use the builtin bisect.bisect function.

from bisect import bisect
inp = open("haybales.in", "r")out = open("haybales.out", "w")
baleNum, queryNum = map(int, inp.readline().split())bales = sorted(list(map(int, inp.readline().split())))for _ in range(queryNum):	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.util.*;import java.io.*;
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 atMost(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, Ordered Set
SilverEasy
Show TagsBinary Search, Sorting
SilverEasy
Show TagsBinary Search, Sorting
SilverNormal
Show TagsBinary Search, Sorting
GoldNormal
Show TagsBinary Search
GoldHard
Show Tags2P, Binary Search, Greedy, Sorting
SilverVery Hard
Show TagsBinary Search, Sqrt
PlatInsane
Show TagsBinary Search, Sorting

### General

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Search
CSESEasy
Show TagsBinary Search
CSESEasy
Show TagsBinary Search
CEOIEasy
Show TagsBinary Search
CFEasy
Show TagsBinary Search
CSESNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search, Prefix Sums
CFNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search
CFNormal
Show TagsBinary Search, Sorting
ACNormal
Show TagsBinary Search, Prefix Sums
CFHard
Show TagsBinary Search, Prefix Sums
CFHard
Show TagsBinary Search
CFHard
Show TagsBinary Search
Baltic OIVery Hard
Show TagsBinary Search

### 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!