Skip to Content
CTRL K

Búsqueda binaria sobre un arreglo ordenado

Recursos

Recursos
FuenteRecursoNotas
CPPlower_bound, upper_bound

con ejemplos

Recursos
FuenteRecursoNotas
JAVAArrays.binarySearch
JAVACollections.binarySearch
Recursos
FuenteRecursoNotas
PythonArray bisection algorithm
GFGBinary Search (bisect) in Python

Video de YouTube (qaQJurNVew8)

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

Conviene revisar el módulo de Búsqueda binaria para recursos adicionales (aunque cubren material extra que no forma parte de este módulo).

Introducción

Figura · el intervalo se parte a la mitad

Clic en un número para buscarlo. El corchete es el rango vivo; la marca es mid.

objetivo=11 · lo=0 · mid=— · hi=6

Buscamos 11. El rango vivo es todo el arreglo.

Ejemplo - Counting Haybales

HechoFuenteNombreDificultadTagsSolución
SilverCounting HaybalesFácilBinary SearchSolución

Explicación

Como cada uno de los puntos está en el rango 0…1 000 000 0000 \ldots 1\,000\,000\,000, guardar las ubicaciones de los fardos en un arreglo booleano y luego tomar sumas de prefijos de ese arreglo tomaría demasiado tiempo y memoria.

En su lugar, pongamos todas las ubicaciones de los fardos en una lista y ordenémosla. Ahora podemos usar búsqueda binaria para contar tanto la cantidad de fardos con posición a lo sumo BB como la cantidad de fardos con posición menor que AA en tiempo O(log⁡N)\mathcal{O}(\log N), y luego restar estas dos cantidades para obtener la respuesta final.

Implementación (sin funciones de la librería)

Complejidad temporal: O((N+Q)log⁡N)\mathcal{O}((N + Q) \log{N})

#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);
	}
}
 
int main() {
	setIO("haybales");
	int bale_num;
	int query_num;
	cin >> bale_num >> query_num;
	vector<int> bales(bale_num);
	for (int &i : bales) { cin >> i; }
 
	sort(begin(bales), end(bales));
	// Returns the number of elements that are at most x
	auto atMost = [&](int x) {
		int lo = 0;
		int hi = bales.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (bales[mid] <= x) {
				lo = mid + 1;
			} else {
				hi = mid;
			}
		}
		return lo;
	};
 
	for (int i = 0; i < query_num; ++i) {
		int q_start;
		int q_end;
		cin >> q_start >> q_end;
		cout << atMost(q_end) - atMost(q_start - 1) << "\n";
	}
}
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];
		for (int i = 0; i < baleNum; i++) { bales[i] = io.nextInt(); }
		Arrays.sort(bales);
 
		for (int i = 0; i < queryNum; ++i) {
			int start = io.nextInt();
			int end = io.nextInt();
			io.println(atMost(end) - atMost(start - 1));
		}
		io.close();
	}
 
	// Returns the number of elements that are at most x
	public static int atMost(int x) {
		int lo = 0;
		int hi = bales.length;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (bales[mid] <= x) {
				lo = mid + 1;
			} else {
				hi = mid;
			}
		}
		return lo;
	}
 
	// CodeSnip{Kattio}
}
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
 
 
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(at_most(end) - at_most(start - 1), file=out)

Implementación (con funciones de la librería)

Complejidad temporal: O((N+Q)log⁡N)\mathcal{O}((N + Q) \log{N})

Podemos usar las funciones de la librería lower_bound y upper_bound.

#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);
	}
}
 
int main() {
	setIO("haybales");
	int bale_num;
	int query_num;
	cin >> bale_num >> query_num;
	vector<int> bales(bale_num);
	for (int i = 0; i < bale_num; i++) { cin >> bales[i]; }
 
	sort(begin(bales), end(bales));
	for (int i = 0; i < query_num; i++) {
		int q_start;
		int q_end;
		cin >> q_start >> q_end;
		cout << upper_bound(begin(bales), end(bales), q_end) -
		            lower_bound(begin(bales), end(bales), q_start)
		     << "\n";
	}
}

Podemos usar la función de la librería Arrays.binarySearch.

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());
		int queryNum = Integer.parseInt(st.nextToken());
		int[] bales = new int[baleNum];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < baleNum; i++) {
			bales[i] = Integer.parseInt(st.nextToken());
		}
 
		Arrays.sort(bales);
		for (int i = 0; i < queryNum; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
 
			// Get the left-est bale that's still in the interval
			int bi = Arrays.binarySearch(bales, start);
			if (bi < 0) { bi = Math.abs(bi + 1); }
 
			// And also get the right-est bale that's still in the interval
			int ti = Arrays.binarySearch(bales, end);
			if (ti < 0) { ti = Math.abs(ti + 2); }
			out.println(ti - bi + 1);
		}
		out.close();
	}
}

Podemos usar la función de la librería bisect.bisect.

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)

Problemas

HechoFuenteNombreDificultadTagsSolución
CFCellular NetworkFácil2P, Binary SearchSolución
SilverCow-libiFácilBinary SearchSolución
LCOnline Majority Element In SubarrayFácilBinary Search—
GoldWalking in ManhattanInsanoBinary Search—
Dos punterosBúsqueda binaria