Cerramos el módulo de grafos diciendo que el siguiente músculo a entrenar era otro: buscar y ordenar dentro de volúmenes de datos. Rutalia acumula millones de filas — el histórico de entregas con su timestamp, el catálogo de productos, las tarifas por tramos de peso — y sobre datos ordenados existe una herramienta que convierte búsquedas de millones de pasos en unas pocas decenas: la búsqueda binaria. Ya la conoces de refilón: en 01-02 analizamos su recurrencia T(n) = T(n/2) + c ("búsqueda en direcciones ordenadas") y concluimos que era O(log n). Esta lección la trabaja a fondo, porque la búsqueda binaria tiene fama merecida de ser la más afilada y la más traicionera de las técnicas básicas: es trivial de enunciar, pero un estudio clásico encontró errores en la mayoría de implementaciones escritas por programadores profesionales. Aprenderás a escribirla con un invariante que la hace a prueba de balas, sus variantes lower_bound/upper_bound, el módulo bisect de Python, y el patrón más potente de todos: la búsqueda binaria sobre la respuesta.

1. La búsqueda binaria clásica y por qué es traicionera
2. El invariante del intervalo: la forma correcta de razonar
3. lower_bound y upper_bound: primera y última ocurrencia
4. El módulo bisect de Python en la práctica
5. Búsqueda binaria sobre la respuesta: el patrón "¿es factible(x)?"
6. Funciones monótonas y una mención a la búsqueda ternaria

La idea es la de siempre: si el array está ordenado, comparo con el elemento central y descarto la mitad que no puede contener lo que busco. Cada comparación divide el problema por dos, de ahí la recurrencia T(n) = T(n/2) + c que resolvimos en 01-02: O(log n). Sobre un histórico de 10 millones de entregas de Rutalia, eso son unas 24 comparaciones frente a las 10.000.000 de un recorrido lineal.

Desglosemos por qué cada línea es como es, porque aquí es donde la gente se corta:

• lo, hi = 0, len(datos) - 1: elegimos representar el intervalo cerrado [lo, hi] — ambos extremos son candidatos válidos. Esta decisión condiciona todo lo demás.
• while lo <= hi: con intervalo cerrado, el intervalo está vacío cuando lo > hi. Escribir lo < hi aquí sería un error: dejaría sin examinar el caso de un único candidato.
• lo = medio + 1 y hi = medio - 1: siempre excluimos medio del nuevo intervalo, porque ya lo hemos examinado. Escribir lo = medio o hi = medio en esta versión provoca el clásico bucle infinito cuando el intervalo se reduce a uno o dos elementos y medio no avanza.

En Python los enteros tienen precisión arbitraria y esta línea es segura. Pero conviene saberlo: en Java, C o C++, (lo + hi) / 2 con enteros de 32 bits desborda cuando lo + hi supera 2³¹ − 1, aunque ambos valores sean índices válidos por separado. Este bug estuvo casi diez años en la búsqueda binaria de la biblioteca estándar de Java (java.util.Arrays.binarySearch) hasta que se detectó en 2006. La forma robusta en esos lenguajes es:

Si algún día portas tu código de Rutalia de Python a un servicio en Java o Go, recuerda esta línea. Es el ejemplo perfecto de por qué la búsqueda binaria es traicionera: el algoritmo es correcto en la pizarra y falla en la máquina.

En 03-03 razonamos Dijkstra con un invariante ("las distancias extraídas del heap son definitivas"). La búsqueda binaria se domina igual: en lugar de memorizar dónde va cada +1, se declara un invariante y se mantiene.

Usemos la convención semiabierta [lo, hi), que es la nativa de Python (slicing, range, bisect). El invariante que elegimos, pensando ya en la variante más útil:

Invariante: todo elemento con índice < lo es estrictamente menor que el objetivo; todo elemento con índice >= hi es mayor o igual que el objetivo.

Gráficamente, el array queda dividido en tres zonas que el bucle va estrechando:

Fíjate en los detalles y compáralos con la versión cerrada:

• Aquí hi = medio sin -1 es correcto, porque hi es exclusivo: asignar hi = medio significa "sé que datos[medio] >= objetivo", exactamente lo que exige el invariante.
• No hay bucle infinito: como lo < hi dentro del bucle, siempre medio < hi, así que hi = medio reduce estrictamente el intervalo, y lo = medio + 1 también.
• Al salir, lo == hi y las dos zonas se tocan: lo es la frontera entre "menores que el objetivo" y "mayores o iguales". Esa frontera es un resultado mucho más rico que un simple "está / no está".

Esta manera de pensar — elige el invariante, escribe cada rama para mantenerlo, y el resultado sale solo — es la que debes interiorizar. Todas las variantes que siguen son el mismo esqueleto con otro invariante.

En datos reales hay duplicados. En el histórico de Rutalia, miles de entregas comparten el mismo día; en las tarifas, varios productos comparten tramo de peso. La pregunta útil casi nunca es "¿está el valor X?" sino "¿dónde empieza y dónde acaba el bloque de X?". Para eso existen dos fronteras:

Con ambas fronteras se responde todo:

• Primera ocurrencia de x: i = lower_bound(a, x); existe si i < len(a) y a[i] == x.
• Última ocurrencia de x: upper_bound(a, x) - 1 (si x existe).
• Número de ocurrencias: upper_bound(a, x) - lower_bound(a, x) — cero si x no está.
• Rango de un intervalo de valores [x, y]: a[lower_bound(a, x) : upper_bound(a, y)].

upper_bound es lower_bound cambiando una comparación (<= en lugar de < al decidir la rama). En Python no hace falta escribirlas: ya vienen hechas.

La biblioteca estándar trae las dos fronteras con nombres propios: bisect_left es lower_bound y bisect_right (alias bisect) es upper_bound. Además, insort_left/insort_right insertan manteniendo el orden (ojo: la inserción en lista es O(n) por el desplazamiento de elementos; lo logarítmico es solo localizar la posición).

Veámoslo sobre el histórico de entregas de Rutalia, ordenado por timestamp. Como siempre, datos ficticios genéricos:

Dos trucos importantes del ejemplo:

• Buscar con tuplas parciales: ("2026-07-01T09:00:00",) es una tupla de un solo elemento; al compararse con tuplas de tres, la comparación lexicográfica decide por el primer campo, que es justo lo que queremos. Para el límite superior añadimos un centinela "muy grande" ("￿") como segundo campo, para incluir todas las entregas de ese instante exacto.
• bisect_left para el inicio, bisect_right para el fin: el patrón universal para extraer rangos con duplicados.

Desde Python 3.10, bisect acepta key=, lo que evita los centinelas:

Rutalia cobra el envío según el peso del paquete, por tramos. Este problema — "dado un valor, ¿en qué tramo cae?" — es exactamente una llamada a bisect:

La elección entre bisect_left y bisect_right aquí no es estética: decide si el límite exacto (2,0 kg) cae en el tramo barato o en el caro. Con bisect_right, 2,0 kg pagaría 5,50 EUR. Es el tipo de detalle de frontera que en producción se traduce en facturación incorrecta — otra muestra del carácter traicionero de esta familia de algoritmos.

Hasta aquí buscábamos en un array. El salto conceptual grande de esta lección es que se puede buscar en el espacio de las respuestas posibles, aunque no exista ningún array. Solo se necesita una propiedad:

Si existe una función factible(x) que responde sí/no y es monótona — si x funciona, todo x' > x también funciona (o al revés) — entonces la respuesta óptima se encuentra por búsqueda binaria sobre x.

El espacio de respuestas tiene esta pinta: NO NO NO NO SÍ SÍ SÍ SÍ. Buscar la frontera entre el último NO y el primer SÍ es exactamente un lower_bound sobre un "array virtual" que nunca materializamos.

La furgoneta de la zona CEN debe repartir una secuencia de paquetes en el orden dado (así vienen paletizados del almacén), en como mucho k viajes. ¿Qué capacidad mínima (kg) necesita la furgoneta?

• ¿Es monótono? Sí: si con capacidad C se puede en k viajes, con C+1 también (la furgoneta grande puede imitar a la pequeña).
• factible(C): se comprueba con un voraz trivial — ir llenando el viaje actual y abrir uno nuevo cuando no cabe. ¿Te suena? Es primo del first-fit del bin packing de 02-02, pero aquí el orden es fijo y el voraz sí es exacto.

Análisis: cada factible cuesta O(n) y hacemos O(log R) llamadas, con R = sum − max; total O(n · log R). La alternativa ingenua de probar capacidades una a una es O(n · R): con pesos en gramos y rangos de toneladas, la diferencia es abismal.

Mismo patrón con otro disfraz: Rutalia tiene m repartidores y el repartidor i tarda t_i minutos por entrega (moto, bici, furgoneta...). ¿Cuál es el mínimo tiempo T para completar n entregas trabajando todos en paralelo?

• factible(T): en T minutos, el repartidor i completa T // t_i entregas. ¿Suman al menos n? Cálculo O(m).
• Monotonía: más tiempo, más entregas. Frontera NO→SÍ.

El patrón mental que debes llevarte: cuando el enunciado pide "el mínimo X tal que..." o "el máximo X tal que...", pregúntate si puedes escribir un factible(x) monótono y barato. Si la respuesta es sí, el problema de optimización se convierte en O(log R) problemas de decisión. En 02-03 buscábamos óptimos podando árboles con cotas; aquí los buscamos estrechando un intervalo. Dos filosofías distintas para el mismo verbo: optimizar.

La búsqueda binaria no necesita un array: necesita monotonía. Sirve igual para resolver f(x) = objetivo con f creciente y continua (bisección numérica, con while hi - lo > 1e-9 en lugar de índices), por ejemplo para calibrar la velocidad media a la que debe circular la flota para cumplir una ventana de entrega.

Si la función no es monótona pero es unimodal (baja y luego sube, como el coste total en función del número de furgonetas: pocas = horas extra, muchas = flota infrautilizada), la herramienta hermana es la búsqueda ternaria: se evalúan dos puntos interiores m1 < m2 y se descarta el tercio que no puede contener el mínimo. También es O(log n). No la desarrollamos más: quédate con que existe y con la palabra clave unimodal para reconocer cuándo aplicarla.

• Mezclar convenciones de intervalo. El 90 % de los bugs vienen de usar hi = len(a) con while lo <= hi, o hi = len(a) - 1 con hi = medio. Elige una convención (recomendamos la semiabierta [lo, hi), la nativa de Python) y anótala en un comentario en la primera línea.
• No verificar el resultado de bisect_left. bisect_left(a, x) devuelve una posición de inserción, no garantiza que x esté: comprueba i < len(a) and a[i] == x antes de dar el elemento por encontrado.
• Buscar en datos no ordenados. La búsqueda binaria sobre un array desordenado no falla ruidosamente: devuelve basura con total confianza. En desarrollo, un assert all(a[i] <= a[i+1] for i in range(len(a)-1)) te salva (quítalo en producción: es O(n) y anula la gracia).
• Bucle infinito en la variante "maximizar". Si buscas el máximo x factible con enteros y mueves lo = medio, el redondeo hacia abajo de (lo + hi) // 2 no avanza cuando hi == lo + 1. Solución: redondear hacia arriba con medio = (lo + hi + 1) // 2 en esa variante.
• Cotas iniciales incorrectas en la búsqueda sobre la respuesta. Si lo no es una cota inferior válida (p. ej. olvidar max(pesos) en el ejemplo de la furgoneta), el verificador puede ejecutarse con capacidades en las que ni siquiera cabe un paquete y devolver resultados sin sentido. Dedica un minuto a justificar ambas cotas.
• Consejo: cuando dudes de una implementación, testéala contra fuerza bruta con arrays aleatorios pequeños, incluidos el vacío y el de un elemento. La búsqueda binaria falla casi siempre en n ∈ {0, 1, 2}.

Ejercicio 1 — Rango de un día en el histórico. Con el historico ordenado por timestamp de la sección de bisect, escribe entregas_del_dia(historico, fecha) que devuelva la lista de entregas cuyo timestamp empieza por fecha (formato "2026-07-01"), usando bisect_left/bisect_right (no recorras la lista entera). El coste debe ser O(log n) + O(k), con k el tamaño del resultado.

Ejercicio 2 — Última entrega antes de un instante. Escribe ultima_entrega_antes(historico, ts) que devuelva la última entrega con timestamp estrictamente menor que ts, o None si no hay ninguna. Pista: ¿qué frontera te da directamente esa posición, bisect_left o bisect_right?

Ejercicio 3 — Máximo peso de paquete admisible. Invirtamos el patrón de la búsqueda sobre la respuesta: Rutalia quiere anunciar el máximo peso por paquete que puede prometer, sabiendo que su furgoneta de capacidad C fija debe seguir completando el reparto de pesos (en orden) en k viajes, y suponiendo que todo paquete que supere el peso anunciado se recorta a ese peso. Escribe peso_maximo_admisible(pesos, k, C) con búsqueda binaria sobre la respuesta. Cuidado con la variante "maximizar" y su bucle infinito.

Solución 1:

El truco es el de la lección: el prefijo "2026-07-01" es menor que cualquier timestamp del día (porque cualquier carácter extra hace mayor a la cadena más larga cuando el prefijo coincide), y el centinela "￿" supera a todos ellos. Coste: dos búsquedas O(log n) más el slice O(k).

Solución 2:

bisect_left da el primer elemento >= ts; el anterior es, por definición del invariante, el último < ts. Con bisect_right habríamos obtenido "la última con timestamp <= ts", la otra semántica habitual — elegir la frontera correcta es el ejercicio.

Solución 3:

La monotonía va al revés que antes: cuanto menor es el peso anunciado, menor la carga total y menos viajes — si x es factible, x−1 también. Por eso la frontera es SÍ→NO, movemos lo = medio al acertar, y eso obliga al redondeo hacia arriba (lo + hi + 1) // 2 para garantizar progreso.

La búsqueda binaria es O(log n) puro: la recurrencia T(n) = T(n/2) + c del módulo 1 convertida en herramienta. Lo esencial de esta lección no es el algoritmo — cabe en diez líneas — sino la disciplina: (1) elegir una convención de intervalo y un invariante, y dejar que ellos escriban las ramas; (2) pensar en fronteras (lower_bound/upper_bound) y no en "está o no está", porque las fronteras responden rangos, conteos y tramos de tarifa; (3) reconocer el patrón de la búsqueda sobre la respuesta: cualquier "mínimo/máximo x tal que factible(x)" monótono se resuelve con O(log R) llamadas a un verificador barato — así calculamos la capacidad mínima de la flota de Rutalia sin probar capacidades una a una.

Todo esto ha dependido de una premisa silenciosa: que los datos ya estaban ordenados. El histórico por timestamp, las tarifas por tramos, el catálogo... alguien tuvo que ordenarlos, y sobre millones de filas eso no se hace de cualquier manera. En la próxima lección (04-02) abrimos la caja de la ordenación: por qué los algoritmos O(n²) mueren a escala, cómo mergesort y quicksort logran O(n log n), por qué esa cota no puede batirse comparando... y cómo, con las cartas adecuadas (los códigos postales de Rutalia, por ejemplo), sí puede batirse.