Introduction Binary Search on Monotonic Functions Finding The Maximum x Such That f(x) = true Implementation 1 Implementation 2 Finding The Minimum x Such That f(x) = true Example - Maximum Median Common Mistakes Mistake 1 - Off By One Mistake 2 - Not Accounting for Negative Bounds Mistake 3 - Integer Overflow Problems USACO General Quiz

Somewhat Frequent

0/26

Binary Search

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

Binary searching on arbitrary monotonic functions.

Edit This Page

Prerequisites

Silver - Binary Search on a Sorted Array

Introduction


CSA	Binary Search	animation, code, lower_bound + upper_bound
CPH	3.3 - Binary Search	code, lower_bound + upper_bound, some applications
CF EDU	Binary Search - Steps 1, 2	videos, problems similar to those covered in this module
KA	Binary Search	plenty of diagrams, javascript implementation
IUSACO	12 - Binary Search	module is based off this
TC	Binary Search	similar material
LC	Python Ultimate Binary Search Template	many problems & applications

When we binary search, 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 Search 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 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 similar 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 $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 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

Div 2 C - Maximum Median

CF - Easy

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

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 $x$ . 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]$ . The current median is $4$ , so to increase the median to $6$ , we have to increase the current median by $2$ and we also have to increase the $5$ 's to $6$ .

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

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

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

If this value is less than or equal to $k$ , then $x$ can be the median, so our check function returns true. Otherwise, $x$ 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.

Problems

USACO

Source	Problem Name	Difficulty	Tags
Silver	Cow Dance Show	Easy	Show Tags Binary Search, Sorted Set
Silver	Convention	Easy	Show Tags Binary Search, Sorting
Silver	Angry Cows	Easy	Show Tags Binary Search, Sorting
Silver	Social Distancing	Normal	Show Tags Binary Search, Sorting
Silver	Bakery	Hard	Show Tags Binary Search
Gold	Angry Cows	Hard	Show Tags 2P, Binary Search, Greedy, Sorting
Silver	Loan Repayment	Very Hard	Show Tags Binary Search, Sqrt
Platinum	Load Balancing	Insane	Show Tags Binary Search, Sorting

General

Source	Problem Name	Difficulty	Tags
CSES	Factory Machines	Easy	Show Tags Binary Search
CSES	Array Division	Easy	Show Tags Binary Search
CF	Guess the K-th Zero (Easy)	Easy	Show Tags Binary Search
CF	Mahmoud & Ehab & Function	Normal	Show Tags Binary Search
CC	TripTastic	Normal	Show Tags 2D Prefix Sums, Binary Search
CSES	Multiplication Table	Normal	Show Tags Binary Search
CF	Edu C: Magic Ship	Normal	Show Tags Binary Search, Prefix Sums
CF	The Meeting Place Cannot Be Changed	Normal	Show Tags Binary Search
CF	Preparing for Merge Sort	Normal	Show Tags Binary Search
CF	Minimizing Difference	Normal	Show Tags Binary Search, Greedy, Prefix Sums
CF	Ammar-utiful Array	Normal	Show Tags Binary Search, Prefix Sums
AC	Handshake	Hard	Show Tags Binary Search, Prefix Sums, Sorting
CF	Max Median	Hard	Show Tags Binary Search, Prefix Sums
CF	Grouped Carriages	Hard	Show Tags Binary Search, Priority Queue
CF	Packmen	Hard	Show Tags Binary Search
CF	Level Generation	Hard	Show Tags Binary Search
Baltic OI	2012 - Mobile	Very Hard	Show Tags Binary Search, Stack

Quiz

What are the worst and best case time complexities for searching for a number in a sorted array of size $n$ 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!

Join Forum

Table of Contents

Binary Search

Prerequisites

Table of Contents

Introduction

Binary Search on Monotonic Functions

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

Implementation 1

Implementation 2

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

Example - Maximum Median

Common Mistakes

Mistake 1 - Off By One

Mistake 2 - Not Accounting for Negative Bounds

Mistake 3 - Integer Overflow

Problems

USACO

General

Quiz

Module Progress:

Join the USACO Forum!

Table of Contents

Binary Search

Prerequisites

Table of Contents

Introduction

Binary Search on Monotonic Functions

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

Implementation 1

Implementation 2

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

Example - Maximum Median

Common Mistakes

Mistake 1 - Off By One

Mistake 2 - Not Accounting for Negative Bounds

Mistake 3 - Integer Overflow

Problems

USACO

General

Quiz

Module Progress:Not Started

Join the USACO Forum!

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

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

Module Progress: