Búsqueda binaria

Recursos

Recursos
Fuente	Recurso	Notas
CSA	Binary Search	animación, código, lower_bound + upper_bound
CPH	3.3 - Binary Search	código, lower_bound + upper_bound, algunas aplicaciones
CF EDU	Binary Search - Steps 1, 2	videos, problemas similares a los cubiertos en este módulo
YouTube	Binary Search Tutorial (C++ and Python)	video, buena explicación
KA	Binary Search	muchos diagramas, implementación en javascript
IUSACO	12 - Binary Search	este módulo se basa en este capítulo
TC	Binary Search	material similar
LC	Python Ultimate Binary Search Template	muchos problemas y aplicaciones

Video de YouTube (qaQJurNVew8)

Nótese que el video de arriba cubre ambos módulos de búsqueda binaria.

Cuando hacemos búsqueda binaria, empezamos con un espacio de búsqueda de tamaño $N$ en el que sabemos que está la respuesta. Cada iteración de la búsqueda binaria corta el espacio de búsqueda a la mitad, así que el algoritmo prueba $\mathcal{O}(\log N)$ valores. Esto es eficiente y mucho mejor que probar cada valor posible del espacio de búsqueda.

Búsqueda binaria sobre funciones monótonas

Digamos que tenemos una función booleana f(x). Por lo general, en estos problemas queremos encontrar el valor máximo o mínimo de $x$ tal que f(x) sea verdadera. De forma similar a cómo la búsqueda binaria sobre un arreglo solo funciona si el arreglo está ordenado, la búsqueda binaria sobre la respuesta solo funciona si la función de respuesta es monótona , es decir, que siempre es no decreciente o siempre es no creciente.

Encontrar el máximo `x` tal que `f(x) = true`

Queremos construir una función lastTrue tal que lastTrue(lo, hi, f) devuelva el último x en el rango [lo,hi] tal que f(x) = true. Si no existe tal x, entonces lastTrue debería devolver lo-1.

Esto se puede hacer con búsqueda binaria si f(x) cumple las dos condiciones siguientes:

Si f(x) = true, entonces f(y) = true para todo $y \leq x$ .
Si f(x) = false, entonces f(y) = false para todo $y \geq x$ .

Por ejemplo, si f(x) está dada por la siguiente función:


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

entonces lastTrue(1, 8, f) = 5 y lastTrue(7, 8, f) = 6.

Implementación 1

Verificar que esta implementación no llama a f sobre ningún valor fuera del rango [lo, hi].

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int last_true(int lo, int hi, function<bool(int)> f) {
	// si ningún valor del rango funciona, devolver lo - 1
	lo--;
	while (lo < hi) {
		// encontrar el medio del rango actual (redondeando hacia arriba)
		int mid = lo + (hi - lo + 1) / 2;
		if (f(mid)) {
			// si mid funciona, entonces todos los números menores que mid también funcionan
			lo = mid;
		} else {
			// si mid no funciona, los valores mayores tampoco funcionarían
			hi = mid - 1;
		}
	}
	return lo;
}
 
int main() {
	// todos los números cumplen la condición (imprime 10)
	cout << last_true(2, 10, [](int x) { return true; }) << endl;
 
	// imprime 5
	cout << last_true(2, 10, [](int x) { return x * x <= 30; }) << endl;
 
	// ningún número cumple la condición (imprime 1)
	cout << last_true(2, 10, [](int x) { return false; }) << endl;
}

Ver Lambda Expressions si no se está familiarizado con la sintaxis usada en la función main.


import java.util.function.Predicate;
 
public class BinarySearch {
	public static void main(String[] args) {
		// todos los números cumplen la condición (imprime 10)
		System.out.println(lastTrue(2, 10, (x) -> true));
 
		// imprime 5
		System.out.println(lastTrue(2, 10, (x) -> x * x <= 30));
 
		// ningún número cumple la condición (imprime 1)
		System.out.println(lastTrue(2, 10, (x) -> false));
	}
 
	public static int lastTrue(int lo, int hi, Predicate<Integer> f) {
		// si ningún valor del rango funciona, devolver lo - 1
		lo--;
		while (lo < hi) {
			// encontrar el medio del rango actual (redondeando hacia arriba)
			int mid = lo + (hi - lo + 1) / 2;
			if (f.test(mid)) {
				// si mid funciona, entonces todos los números menores que mid también funcionan
				lo = mid;
			} else {
				// si mid no funciona, los valores mayores tampoco funcionarían
				hi = mid - 1;
			}
		}
		return lo;
	}
}

Ver la interfaz Predicate de Java si no se está familiarizado con la interfaz Predicate que se usa.


from typing import Callable
 
 
def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
	"""
	Búsqueda binaria
	:param lo: cota inferior
	:param hi: cota superior
	:param f: una función que indica si un número es válido o no
	:return: el máximo x tal que f(x) es verdadero
	"""
	# si ningún valor del rango funciona, devolver lo - 1
	lo -= 1
	while lo < hi:
		# encontrar el medio del rango actual (redondeando hacia arriba)
		mid = lo + (hi - lo + 1) // 2
		if f(mid):
			# si mid funciona, entonces todos los números menores que mid también funcionan
			lo = mid
		else:
			# si mid no funciona, los valores mayores tampoco funcionarían
			# así que los excluimos
			hi = mid - 1
	return lo
 
 
# todos los números cumplen la condición (imprime 10)
print(last_true(2, 10, lambda x: True))
 
# imprime 5
print(last_true(2, 10, lambda x: x * x <= 30))
 
# ningún número cumple la condición (imprime 1)
print(last_true(2, 10, lambda x: False))

Ver Lambda Expressions si no se está familiarizado con la sintaxis usada en el programa.

Implementación 2

Este enfoque se basa en saltos de intervalo. En esencia, empezamos desde el comienzo del arreglo, damos saltos y reducimos la longitud del salto a medida que nos acercamos al elemento objetivo. Usamos potencias de 2, de forma muy similar a Binary Jumping.

C++JavaPython


#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;
}


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;
}


from typing import Callable
 
 
def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
	"""
	Búsqueda binaria
	:param lo: cota inferior
	:param hi: cota superior
	:param f: una función que indica si un número es válido o no
	:return: el máximo x tal que f(x) es verdadero
	"""
	lo -= 1
	dif = hi - lo
	while dif > 0:
		while lo + dif <= hi and f(lo + dif):
			lo += dif
		dif //= 2
	return lo

Encontrar el mínimo `x` tal que `f(x) = true`

Queremos construir una función firstTrue tal que firstTrue(lo, hi, f) devuelva el primer x en el rango [lo,hi] tal que f(x) = true. Si no existe tal x, entonces firstTrue debería devolver hi+1.

De forma similar a la parte anterior, esto se puede hacer con búsqueda binaria si f(x) cumple las dos condiciones siguientes:

Si f(x) es verdadera, entonces f(y) es verdadera para todo $y \geq x$ .
Si f(x) es falsa, entonces f(y) es falsa para todo $y \leq x$ .

Vamos a hacer lo mismo, pero cuando la condición se cumple cortaremos la parte derecha, y cuando no se cumple se cortará la parte izquierda.

C++JavaPython


#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 {
			lo = mid + 1;
		}
	}
	return lo;
}
 
int main() {
	// imprime 2
	cout << first_true(2, 10, [](int x) { return true; }) << endl;
	// imprime 6
	cout << first_true(2, 10, [](int x) { return x * x >= 30; }) << endl;
	// imprime 11
	cout << first_true(2, 10, [](int x) { return false; }) << endl;
}


import java.util.function.Predicate;
 
public class BinarySearch {
	public static void main(String[] args) {
		System.out.println(firstTrue(2, 10, (x) -> true));         // imprime 2
		System.out.println(firstTrue(2, 10, (x) -> x * x >= 30));  // imprime 6
		System.out.println(firstTrue(2, 10, (x) -> false));        // imprime 11
	}
 
	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;
	}
}


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
 
 
print(first_true(2, 10, lambda x: True))  # imprime 2
print(first_true(2, 10, lambda x: x * x >= 30))  # imprime 6
print(first_true(2, 10, lambda x: False))  # imprime 11

Ejemplo - Maximum Median

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	Div 2 C - Maximum Median	Fácil	Binary Search	en el módulo

Enunciado: Dado un arreglo $\texttt{arr}$ de $n$ enteros, donde $n$ es impar, podemos realizar la siguiente operación sobre él $k$ veces: tomar cualquier elemento del arreglo e incrementarlo en $1$ . Queremos hacer que la mediana del arreglo sea lo más grande posible después de $k$ operaciones.

Restricciones: $1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$ y $n$ es impar.

Para obtener la mediana actual, primero ordenamos el arreglo en orden ascendente.

Ahora, nótese que para aumentar el valor actual a un valor, digamos $x$ . Todos los valores que actualmente son mayores o iguales que la mediana deben seguir siendo mayores o iguales que la mediana.

Por ejemplo, digamos que tenemos el arreglo ordenado $[1,1,2,3,4,4,5,5,6,8,8]$ . La mediana actual es $4$ , así que para aumentar la mediana a $6$ , tenemos que aumentar la mediana actual en $2$ y también tenemos que aumentar los $5$ a $6$ .

Siguiendo esta idea, para aumentar la mediana a $x$ , necesitamos aumentar todos los valores de la segunda mitad del arreglo a algún valor mayor o igual que $x$ .

Luego, hacemos búsqueda binaria por la mediana máxima posible. Sabemos que la cantidad de operaciones necesarias para subir la mediana a $x$ aumenta de forma monótona a medida que $x$ aumenta, así que podemos usar búsqueda binaria. Para un valor de mediana dado $x$ , la cantidad de operaciones necesarias para subir la mediana a $x$ es

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

Si este valor es menor o igual que $k$ , entonces $x$ puede ser la mediana, así que nuestra función de verificación devuelve true. En caso contrario, $x$ no puede ser la mediana, así que nuestra función de verificación devuelve false.

C++JavaPython


#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 {
			hi = mid - 1;
		}
	}
	return lo;
}
 
int main() {
	int size;
	int max_ops;
	cin >> size >> max_ops;
	vector<int> arr(size);
	for (int &i : arr) { cin >> i; }
 
	sort(arr.begin(), arr.end());
	// Usar 2e9 en lugar de INT32_MAX para evitar desbordamiento
	cout << last_true(1, 2e9, [&](int x) {
		// Devuelve true si la mediana se puede subir a x
		long long ops_needed = 0;
		for (int i = (size - 1) / 2; i < size; i++) {
			ops_needed += max(0, x - arr[i]);
		}
		return ops_needed <= max_ops;
	}) << endl;
}

Acá escribimos la función de verificación como una expresión lambda.


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();
 
		size = io.nextInt();
		maxOps = io.nextInt();
		arr = new int[size];
		for (int i = 0; i < size; i++) { arr[i] = io.nextInt(); }
		Arrays.sort(arr);
 
		// Usar 2e9 en lugar de Integer.MAX_VALUE para evitar desbordamiento
		io.println(lastTrue(1, (int)2e9));
		io.close();
	}
 
	public static boolean medReachable(int x) {
		// Devuelve true si la mediana se puede subir a x
		long opsNeeded = 0;
		for (int i = (size - 1) / 2; i < size; i++)
			opsNeeded += Math.max(0, x - arr[i]);
		return opsNeeded <= maxOps;
	}
 
	public static int lastTrue(int lo, int hi) {
		lo--;
		while (lo < hi) {
			int mid = lo + (hi - lo + 1) / 2;
			if (medReachable(mid)) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		return lo;
	}
 
	// CodeSnip{Kattio}
}


from typing import Callable
 
 
def med_reachable(x: int) -> bool:
	"""
	Comprueba si la cantidad de operaciones dadas alcanza
	para subir la mediana del arreglo a x.
	"""
	ops_needed = 0
	for i in range((size - 1) // 2, size):
		ops_needed += max(0, x - arr[i])
	return ops_needed <= max_ops
 
 
# búsqueda binaria de la respuesta correcta
def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
	lo -= 1
	while lo < hi:
		mid = lo + (hi - lo + 1) // 2
		if f(mid):
			lo = mid
		else:
			hi = mid - 1
	return lo
 
 
size, max_ops = map(int, input().split())
arr = sorted(list(map(int, input().split())))
print(last_true(1, int(2e9), med_reachable))

Errores comunes

Error 1 - Error por uno

Consideremos el código de Binary Search on Functions de CSAcademy.

C++JavaPython


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;
}


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;
}


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

¡Esto produce un ciclo infinito si left=0 y right=1! Para corregirlo, hay que poner middle = (left+right+1)/2 en su lugar.

Error 2 - No contemplar cotas negativas

Consideremos una versión ligeramente modificada de firstTrue:

C++JavaPython


#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;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}


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;
}


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

¡Este código no necesariamente funciona si lo es negativo! Consideremos el siguiente ejemplo:

C++JavaPython


int main() {
	// imprime -8 en lugar de -9
	cout << first_true(-10, -10, [](int x) { return false; }) << "\n";
 
	// causa un ciclo infinito
	cout << first_true(-10, -10, [](int x) { return true; }) << "\n";
}


public static void main(String[] args) {
	// imprime -8 en lugar de -9
	System.out.println(firstTrue(-10, -10, (x) -> false));
 
	// causa un ciclo infinito
	System.out.println(firstTrue(-10, -10, (x) -> true));
}


# imprime -8 en lugar de -9
print(first_true(-10, -10, lambda x: False))
 
# causa un ciclo infinito
print(first_true(-10, -10, lambda x: True))

Esto ocurre porque dividir un entero negativo impar por dos lo redondea hacia arriba en lugar de hacia abajo.

C++JavaPython


#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;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}


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;
}


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

Error 3 - Desbordamiento de enteros

La primera versión de firstTrue no funciona si hi-lo supera inicialmente INT_MAX, mientras que la segunda versión de firstTrue no funciona si lo+hi supera INT_MAX en algún momento de la ejecución. Si esto es un problema, hay que usar long longs en lugar de ints.

Problemas

USACO

Fuente	Nombre	Dificultad	Tags	Solución
Silver	Cow Dance Show	Fácil	Binary Search, Sorted Set	Solución
Silver	Convention	Fácil	Binary Search, Sorting	Solución
Silver	Angry Cows	Fácil	Binary Search, Sorting	Solución
Silver	Social Distancing	Normal	Binary Search, Sorting	Solución
Gold	★ Angry Cows	Difícil	Binary Search, Sorting, 2P, Greedy	Solución
Silver	Loan Repayment	Difícil	Binary Search, Sqrt	Solución
Silver	Bakery	Muy difícil	Binary Search	—
Gold	Cowdependence	Muy difícil	Binary Search, Prefix Sums, Two Pointers, Sqrt	—
Platinum	Load Balancing	Insano	Binary Search, Sorting	Solución

General

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Factory Machines	Fácil	Binary Search	Solución
CSES	★ Array Division	Fácil	Binary Search	Solución
CF	Guess the K-th Zero (Easy)	Fácil	Binary Search	Solución
CF	Mahmoud & Ehab & Function	Normal	Binary Search	Solución
CC	TripTastic	Normal	2D Prefix Sums, Binary Search	Solución
CSES	Multiplication Table	Normal	Binary Search	Solución
CF	★ Edu C: Magic Ship	Normal	Binary Search, Prefix Sums	Solución
CF	★ The Meeting Place Cannot Be Changed	Normal	Binary Search	Solución
CF	Preparing for Merge Sort	Normal	Binary Search	Solución
CF	Minimizing Difference	Normal	Binary Search, Prefix Sums, Greedy	Solución
CF	Ammar-utiful Array	Normal	Binary Search, Prefix Sums	Solución
CF	Packmen	Normal	Binary Search	Solución
AC	Handshake	Difícil	Binary Search, Prefix Sums, Sorting	Solución
CF	Max Median	Difícil	Binary Search, Prefix Sums	Solución
CF	Grouped Carriages	Difícil	Binary Search, Priority Queue	—
CF	Level Generation	Difícil	Binary Search	Solución
Baltic OI	2012 - Mobile	Muy difícil	Binary Search, Stack	Solución

Quiz

Pregunta 1/4

¿Cuáles son las complejidades temporales del peor y del mejor caso para buscar un número en un arreglo ordenado de tamaño

n

con el siguiente código?

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;
}

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;
}

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

Búsqueda binaria

Recursos

Búsqueda binaria sobre funciones monótonas

Encontrar el máximo x tal que f(x) = true

Implementación 1

Implementación 2

Encontrar el mínimo x tal que f(x) = true

Ejemplo - Maximum Median

Errores comunes

Error 1 - Error por uno

Error 2 - No contemplar cotas negativas

Error 3 - Desbordamiento de enteros

Problemas

USACO

General

Quiz

Encontrar el máximo `x` tal que `f(x) = true`

Encontrar el mínimo `x` tal que `f(x) = true`