Búsqueda binaria
En resumen: La búsqueda binaria encuentra un valor en un arreglo ordenado comparando con la mitad y descartando la otra mitad cada vez: O(log n) comparaciones.
Problema
El filtro que lee todo el catálogo
La tienda tiene 1 000 000 de productos, y la lista de precios está ordenada por precio. El filtro «precio exacto» busca con un bucle desde el principio, como la búsqueda lineal. Los precios en el código están en céntimos de euro: de 2 a 2 000 000. Un cliente busca un producto a 20.000,01 €, y no hay ninguno:
n = 1_000_000prices = [2 * (i + 1) for i in range(n)]target = 2 * n + 1
comparisons = 0found = -1for i in range(n): comparisons += 1 if prices[i] == target: found = i breakprint(f"Índice: {found}")print(f"Comparaciones: {comparisons}")Índice: -1Comparaciones: 1000000Un millón de comparaciones para decir «ninguno». Y cada vez que se abre la página, el filtro se ejecuta para decenas de precios.
Los precios están ordenados, y el bucle no lo aprovecha. Cuando buscas una palabra en un diccionario, no lees desde la primera página. Lo abres por la mitad y ves si la palabra va antes o después.
La idea
Pregunta por la mitad, descarta la otra mitad
Mira el precio de la mitad de la lista:
- si es el que buscas, terminaste;
- si es menor, el que buscas solo puede estar a la derecha. La mitad izquierda queda fuera, junto con la del medio;
- si es mayor, el que buscas solo puede estar a la izquierda.
Después, lo mismo con la mitad que queda. Esto es la búsqueda binaria. El rango donde el precio aún puede estar se guarda con dos índices: lo (el comienzo) y hi (el final). La mitad es mid.
Cada comparación reduce el rango a la mitad. 1 000 000 de precios pasan a 500 000, luego a 250 000, y tras unas 20 reducciones queda uno. Cuántas veces divides entre 2 hasta llegar a 1 se llama logaritmo en base 2: log₂ 1 000 000 ≈ 20. Por eso la búsqueda binaria es O(log n) y la lineal es O(n).
Hay una condición: el arreglo debe estar ordenado. En un arreglo sin ordenar, «es menor, así que está a la derecha» no es cierto.
Míralo
lo, mid y hi en la lista de precios
def find(prices, target): lo = 0 hi = len(prices) - 1 while lo <= hi: mid = (lo + hi) // 2 if prices[mid] == target: return mid elif prices[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]print(f"Índice: {find(prices, 49)}")Índice: 12def find(prices, target): lo = 0 hi = len(prices) - 1 while lo <= hi: mid = (lo + hi) // 2 if prices[mid] == target: return mid elif prices[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1Paso a paso, en palabras
- La lista de precios está ordenada: 15 precios. Buscamos 49 €. lo y hi abarcan todo, de 0 a 14.
- mid = 7: 27 € < 49 €, así que el precio está a la derecha. lo = 8, la parte izquierda queda fuera. Quedan 7 precios.
- mid = 11: 44 € < 49 €, así que el precio está a la derecha. lo = 12, la parte izquierda queda fuera. Quedan 3 precios.
- mid = 13: 53 € > 49 €, así que el precio está a la izquierda. hi = 12, la parte derecha queda fuera. Queda 1 precio.
- mid = 12: 49 €. Ese es el precio buscado: find devuelve 12.
- 4 comparaciones. Una búsqueda desde el principio habría mirado 13 precios; con 1 000 000 de precios la búsqueda binaria necesita como máximo 20.
(lo + hi) // 2: // divide y redondea hacia abajo a un número entero. En Java y C# se escribe distinto, porque allí la suma puede desbordarse. En Python no puede: una de las siguientes tarjetas dice por qué.Más precisamente, para curiosos
El peor caso es que el precio no esté: el rango se divide a la mitad hasta que lo pasa a hi. Con n precios son como máximo ⌊log₂ n⌋ + 1 comparaciones: 4 para 10 precios, 10 para 1000, 20 para 1 000 000. El mejor caso es una comparación: el precio está justo en la mitad.
Aquí una «comparación» es una prueba de mid. La comprobación de igual y la de menor son dos líneas en el código, pero preguntan por el mismo precio.
Pruébalo
Predice cuántas pruebas
Precios ordenados en céntimos de euro: 2, 4, 6, …, 2000. Buscamos 2001, y no existe ese precio. ¿Cuántas veces se ejecuta el bucle?
n = 1000prices = [2 * (i + 1) for i in range(n)]target = 2 * n + 1
steps = 0lo = 0hi = n - 1while lo <= hi: mid = (lo + hi) // 2 steps += 1 if prices[mid] == target: break elif prices[mid] < target: lo = mid + 1 else: hi = mid - 1print(steps)1000 precios, y cada prueba reduce el rango a la mitad: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1. Son 10 pruebas. La búsqueda lineal compararía los 1000.
Pruébalo
Completa
El precio en mid es menor que el que buscas. ¿Dónde empieza el nuevo rango?
def find(prices, target):
lo = 0
hi = len(prices) - 1
while lo <= hi:
mid = (lo + hi) // 2
if prices[mid] == target:
return mid
elif prices[mid] < target:
lo =
else:
hi = mid - 1
return -1El precio que buscas está a la derecha de mid, y mid ya está comprobado. Así que el nuevo comienzo es mid + 1. Si escribes lo = mid, cuando lo y hi están juntos la mitad vuelve a ser lo y el bucle no avanza.
La idea
Los límites: donde todos se equivocan
La búsqueda binaria se escribe en seis líneas y es famosa por escribirse mal. El error casi siempre es por uno: < en lugar de <=, mid en lugar de mid - 1. Se llama error off-by-one.
Te proteges con una decisión: qué significan lo y hi. Después te atienes a ella en todas partes.
- Rango cerrado
[lo, hi]: ambos extremos pueden ser el precio.hiempieza en el último índice, el bucle se ejecuta mientraslo <= hi, y la mitad se descarta conhi = mid - 1ylo = mid + 1. Ese es elfindde arriba. - Rango semiabierto
[lo, hi):hies el primer lugar después del rango.hiempieza en la longitud del arreglo, el bucle se ejecuta mientraslo < hi, y se va a la izquierda conhi = mid, porquehino está en el rango de todos modos.
Los dos son correctos. El error es mezclarlos. Aquí hay un rango cerrado con hi = mid del semiabierto. Buscamos 4 €, y no existe ese precio. Un tope detiene el bucle tras 8 pruebas; de lo contrario no terminaría nunca:
def find(prices, target): lo = 0 hi = len(prices) - 1 probes = 0 while lo <= hi: mid = (lo + hi) // 2 print(f"lo={lo} hi={hi} mid={mid}") probes += 1 if probes == 8: print("Me detengo tras 8 intentos: lo y hi no se mueven") return -1 if prices[mid] == target: return mid elif prices[mid] < target: lo = mid + 1 else: hi = mid return -1prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]find(prices, 4)lo=0 hi=14 mid=7lo=0 hi=7 mid=3lo=0 hi=3 mid=1lo=0 hi=1 mid=0lo=1 hi=1 mid=1lo=1 hi=1 mid=1lo=1 hi=1 mid=1lo=1 hi=1 mid=1Me detengo tras 8 intentos: lo y hi no se muevenCuando lo y hi valen 1, la mitad es 1, el precio ahí es 5 €, más que 4 €, y hi = mid vuelve a ser 1. Nada cambia. Esto es un bucle infinito: el programa no falla, se queda colgado.
Pruébalo
Encuentra el error
La búsqueda encuentra 49 €, pero no encuentra el producto más caro, 58 €, aunque está en la lista de precios:
prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]print(f"Índice: {find(prices, 58)}")Índice: -1Elige la línea con el error.
El rango es cerrado: hi empieza en el último índice, así que también hay que comprobar el precio en hi. Con lo < hi el bucle termina cuando lo y hi están en el mismo precio, sin mirarlo. Para 58 € es la última prueba: lo y hi llegan a 14 y el bucle acaba. La corrección es lo <= hi, y la búsqueda devuelve 14.
La idea
Cuando (lo + hi) / 2 se desborda
En Java y C# un int llega hasta 2 147 483 647, y con un arreglo de más de mil millones de elementos (lo + hi) / 2 se desborda: la suma se convierte en un número negativo. Por eso allí la mitad se escribe lo + (hi - lo) / 2.
En Python los enteros no tienen límite superior. La suma es un número más grande, nada más:
lo = 1_500_000_000hi = 2_000_000_000print((lo + hi) // 2)print(lo + (hi - lo) // 2)17500000001750000000(lo + hi) // 2 es correcto con cualquier tamaño. lo + (hi - lo) // 2 también funciona, pero aquí no protege de nada.
Más precisamente, para curiosos
El error no es inventado. La búsqueda binaria de la biblioteca estándar de Java, Arrays.binarySearch, tuvo (low + high) / 2 durante nueve años. Joshua Bloch lo describió en 2006 en el artículo «Nearly All Binary Searches and Mergesorts are Broken»: un programa con un arreglo de más de 2³⁰ elementos falla con ArrayIndexOutOfBoundsException. Hoy ahí dice (low + high) >>> 1.
Míralo
El primer precio desde 20 €
El filtro «precio desde 20 €» no busca un precio exacto. Busca el primer lugar donde el precio es al menos 20 €: desde ahí están todos los productos que debe mostrar. Esto se llama límite inferior (lower bound). También es la primera aparición: si entre los precios hay tres productos a 15 €, el límite inferior de 15 es el primero de ellos.
find no lo da: se detiene en el primer 15 que pisa. El límite inferior usa un rango semiabierto, y el bucle no se detiene cuando son iguales, sigue yendo a la izquierda:
def lower_bound(prices, target): lo = 0 hi = len(prices) while lo < hi: mid = (lo + hi) // 2 if prices[mid] < target: lo = mid + 1 else: hi = mid return loprices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]print(f"find: {find(prices, 15)}")first = lower_bound(prices, 15)print(f"El primer 15 €: índice {first}")print(f"Productos a 15 €: {lower_bound(prices, 16) - first}")from20 = lower_bound(prices, 20)print(f"El primer precio desde 20 €: {prices[from20]} €")find: 5El primer 15 €: índice 4Productos a 15 €: 3El primer precio desde 20 €: 24 €Si el precio es menor que el que buscas, él y todo lo anterior quedan fuera: lo = mid + 1. Si no, mid puede ser la respuesta, así que se queda en el rango: hi = mid. El bucle termina cuando lo y hi se juntan, y ahí está el primer lugar con un precio ≥ al buscado. Si no hay tal lugar, lo es la longitud del arreglo. Cuántos productos cuestan 15 € es la diferencia entre dos límites inferiores: el de 16 y el de 15.
En Python el límite inferior viene listo: el módulo bisect. bisect_left es exactamente el lower_bound de arriba, y bisect_right da el primer lugar con un precio mayor que el buscado:
import bisect
prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]print(bisect.bisect_left(prices, 24))print(bisect.bisect_left(prices, 20))print(bisect.bisect_left(prices, 15))print(bisect.bisect_right(prices, 15))8847bisect_right(prices, 15) - bisect_left(prices, 15) es cuántos productos cuestan 15 €. Si el precio exacto está, lo compruebas así: i < len(prices) and prices[i] == x. bisect.insort pone un elemento nuevo en su lugar en una lista ordenada.
Míralo
Mídelo: lineal contra binaria
Búsqueda lineal y binaria en la misma lista de precios ordenada, cuando el precio no está. La búsqueda lineal compara todos los precios: n comparaciones. La binaria hace 20 comparaciones con 1 000 000 de precios:
- Búsqueda lineal (cada precio)
O(n) - Búsqueda binaria
O(log n)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 | n = 1.000.000 |
|---|---|---|---|---|
| Búsqueda lineal (cada precio) | 10 | 1000 | 100.000 | 1.000.000 |
| Búsqueda binaria | 4 | 10 | 17 | 20 |
def find(prices, target): lo = 0 hi = len(prices) - 1 while lo <= hi: mid = (lo + hi) // 2 if prices[mid] == target: return mid elif prices[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1La curva binaria casi está plana: con 100 veces más precios sube unas 7 comparaciones. Por eso la búsqueda binaria está en todas partes donde algo está ordenado: índices de bases de datos, git bisect, encontrar la versión en la que una prueba empezó a fallar.
Ejercicio
El filtro de precios: de 10 € a 30 €
Resuélvelo en tu editor.
De 10 € a 30 €. El filtro muestra cuántos productos cuestan de 10 € a 30 € inclusive. La lista de precios está ordenada: 3 €, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 y 49. No recorras todo el arreglo: con dos búsquedas binarias encuentra el primer lugar con un precio ≥ 10 € y el primero con un precio ≥ 31 €. La diferencia es la cantidad.
De 10 € a 30 €: 7 productosMás tareas
- La última aparición. Escribe
upper_bound: el primer lugar con un precio mayor que el buscado. El último producto a 15 € está un lugar antes. - Un hueco de entrega libre. Los huecos de entrega libres son un arreglo ordenado de minutos después de medianoche (540 son las 9:00). El cliente quiere la entrega no antes de las 14:10. Encuentra el primer hueco libre, o di que no hay.
- Dónde va el precio nuevo. Un producto nuevo a 21 € tiene que entrar en la lista de precios de modo que siga ordenada. Encuentra el lugar con búsqueda binaria.
Test