Llevamos tres lecciones prometiéndola: la anticipamos en 01-01 como motivación, en 01-03 la usamos para ilustrar el crecimiento logarítmico, y el Módulo 3 cerró llamándola "la joya de la eficiencia logarítmica". Ha llegado el momento de pagar la deuda. La búsqueda binaria localiza un elemento en una colección ordenada descartando la mitad de los candidatos en cada paso: donde buscar_parada (02-03) necesitaba hasta 40 comparaciones para encontrar una parada en una línea de 40, la búsqueda binaria necesita 6. En esta lección la implementaremos con cuidado quirúrgico — es célebre por concentrar errores sutiles en cuatro líneas —, la trazaremos sobre el catálogo de paradas de RutaBus, la analizaremos con las herramientas del Módulo 2 y la conectaremos con su estrategia madre: divide y vencerás (03-01).

1. El requisito innegociable: una colección ordenada
2. Implementación iterativa con invariantes
3. Traza paso a paso: buscar una parada por código
4. Versión recursiva
5. Análisis: por qué O(log n)
6. Búsqueda binaria contra búsqueda lineal
7. Variantes útiles: primera ocurrencia y el módulo bisect

La búsqueda binaria hace una apuesta: mira el elemento central y, comparándolo con el objetivo, decide en qué mitad no puede estar. Esa deducción solo es válida si la colección está ordenada. Si el elemento central es menor que el objetivo, todo lo que hay a su izquierda también lo es — y podemos descartarlo en bloque sin mirarlo. Sin orden, no hay deducción posible: descartar una mitad sería tirar una moneda.

El catálogo central de paradas de RutaBus asigna a cada parada un código alfabético. Mantenido en orden, es el escenario perfecto:

¿Y si la lista no está ordenada? Ordenarla tiene su propio coste y sus propios algoritmos — exactamente el tema de las tres próximas lecciones (04-02 a 04-04). Aquí asumimos el orden como dado; la regla práctica de cuándo compensa ordenar para luego buscar la veremos al comparar costes en el apartado 6.

La versión iterativa es la canónica. Cada línea tiene una justificación precisa:

La herramienta para razonar sobre este bucle es su invariante: una afirmación que es cierta antes de cada vuelta. Aquí es:

Si objetivo está en la lista, su índice está en el rango [izq, der].

Cada pieza del código existe para preservar ese invariante:

• medio = (izq + der) // 2: el índice central del rango vigente (la división entera // redondea hacia abajo cuando el rango tiene tamaño par). Elegir el centro es lo que garantiza que, decidamos lo que decidamos, descartamos la mitad de los candidatos — ni más ni menos.
• izq = medio + 1 (y no izq = medio): ya hemos comprobado que lista[medio] != objetivo, así que medio deja de ser candidato. Saltárselo no rompe el invariante (el objetivo no puede estar ahí) y es lo que garantiza que el rango siempre se encoge — la clave para que el bucle termine.
• der = medio - 1: el argumento simétrico.
• while izq <= der: el rango [izq, der] contiene der - izq + 1 elementos; cuando izq > der contiene cero. En ese momento el invariante dice: "si estuviera, estaría en un rango vacío" — es decir, no está. Por eso el return -1 de después del bucle es correcto, no un parche.

Fíjate en que el razonamiento por invariante convierte "me suena que funciona" en una demostración: invariante cierto al inicio (todo el rango es candidato), preservado en cada vuelta, y rango estrictamente menguante → el algoritmo termina y su respuesta es correcta.

Busquemos el código "PMA" (Plaza Mayor) en la lista de 9 códigos. Los índices van de 0 a 8:

Tres comparaciones para 9 elementos. La búsqueda lineal habría necesitado 6 (recorre AVP, ESN, HCE, MVJ, PDR, PMA). Observa la mecánica de descarte: tras la primera comparación quedan 4 candidatos; tras la segunda, 1. Cada vuelta reduce el rango a la mitad (a veces algo menos de la mitad, nunca más).

Y una búsqueda fallida, "HOS" (un código que no existe):

Cuatro comparaciones para certificar la ausencia entre 9 elementos. Recuerda de 02-03 que en la búsqueda lineal verificar la ausencia obliga a mirarlo todo (n comparaciones); aquí basta log n — la ausencia se certifica al mismo precio que la presencia.

La estructura "descarta una mitad y repite" es naturalmente recursiva, y de hecho es un caso de divide y vencerás degenerado: se divide en dos mitades pero solo se conquista una (la otra se descarta), y no hay nada que combinar:

Misma lógica, mismas comparaciones. La diferencia está en el espacio: cada llamada pendiente ocupa un marco en la pila (02-02), así que la recursiva usa O(log n) de espacio auxiliar frente al O(1) de la iterativa. Como además Python no optimiza la recursión de cola, en la práctica se prefiere la iterativa; la recursiva vale como puente conceptual hacia los algoritmos de 04-03 y 04-04, que sí necesitan la recursión de verdad.

Apliquemos el método de contar mitades, el mismo conteo de niveles de 03-01. Cada comparación fallida reduce el número de candidatos, como mínimo, a la mitad:

La pregunta "¿cuántas veces puedo dividir n entre 2 hasta llegar a 1?" tiene nombre desde 01-03: log₂ n. El peor caso hace pues ⌊log₂ n⌋ + 1 comparaciones → O(log n). Es la recurrencia T(n) = T(n/2) + O(1): un solo subproblema de tamaño mitad más trabajo constante — compárala con la T(n) = 2·T(n/2) + O(n) que dejamos pendiente en 03-01 y que resolveremos en 04-03.

Los tres casos, con el criterio de 02-03:

• Mejor caso — Θ(1): el objetivo está justo en el primer medio. Una comparación.
• Peor caso — Θ(log n): el objetivo está en una "hoja" del proceso de división, o no está.
• Caso promedio — Θ(log n): la mayoría de los elementos necesitan cerca de log n pasos (la mitad de los elementos solo se alcanzan en el último nivel), así que el promedio queda a una o dos comparaciones del peor caso.

Espacio: O(1) auxiliar en la iterativa (tres variables), O(log n) en la recursiva por la pila.

Enfrentemos a la recién llegada con buscar_parada de 02-03:

Para hacerse una idea física: con el catálogo nacional de 1.000.000 de paradas, la lineal promedia 500.000 comparaciones; la binaria, 20. Es la diferencia entre jerarquías de 01-03 hecha carne.

La letra pequeña es el requisito previo. Si la lista cambia constantemente y solo vas a buscar una vez, ordenar primero (que costará O(n log n), como veremos) para ahorrar en una búsqueda es un mal negocio: la lineal gana. La búsqueda binaria brilla cuando el coste de ordenar se amortiza entre muchas búsquedas — un catálogo que se ordena una vez al desplegarse y se consulta millones de veces al día, como el de RutaBus.

Nuestra busqueda_binaria devuelve algún índice donde está el objetivo. Si hay duplicados — varias llegadas con la misma hora en un panel — a menudo queremos el primero. El truco: al encontrar una coincidencia, no pares; anótala y sigue buscando a la izquierda:

Sigue siendo O(log n): no hemos añadido vueltas, solo hemos cambiado qué hacemos al acertar. El invariante ahora es "resultado es la ocurrencia más a la izquierda vista hasta ahora, y si hay una anterior está en [izq, der]".

Python trae la búsqueda binaria de fábrica en el módulo bisect — de hecho ya lo usamos sin explicarlo en registrar_llegada (02-03, ejercicio 3):

Dos matices que confunden al principio:

• bisect_left/bisect_right no dicen si el elemento está: devuelven el punto de inserción que mantiene el orden. Para saber si está: i = bisect_left(lista, x) y comprobar i < len(lista) and lista[i] == x — que es exactamente primera_ocurrencia gratis.
• insort busca en O(log n) pero inserta en O(n) por el desplazamiento de list.insert — la conclusión del ejercicio de 02-03 sigue vigente: la búsqueda binaria acelera el encontrar, no el mover.

• Aplicarla a una lista sin ordenar. El error número uno, y el más traicionero: no lanza excepción, simplemente devuelve resultados erróneos a veces. Si tienes dudas, assert lista == sorted(lista) en desarrollo.
• Off-by-one en los límites. der = len(lista) en vez de len(lista) - 1, o while izq < der en vez de <=: ambos hacen que el último candidato nunca se examine (búsquedas que "no encuentran" elementos presentes en los bordes). Decide un convenio — aquí, rango cerrado [izq, der] — y sé coherente con él en las tres líneas que dependen de él.
• Bucle infinito por no encoger el rango. Escribir izq = medio (sin + 1) parece inocente, pero con un rango de 2 elementos medio == izq y el rango ya no cambia: bucle eterno. La regla de oro: tras cada vuelta, medio debe quedar fuera del nuevo rango.
• La anécdota del overflow. Durante décadas, la implementación de referencia en Java calculaba medio = (izq + der) / 2; en 2006 se descubrió que con arrays de más de 2³⁰ elementos la suma izq + der desbordaba el entero de 32 bits y producía un índice negativo. La corrección clásica es medio = izq + (der - izq) // 2. En Python no puede pasar — los enteros son de precisión arbitraria —, pero la conocerás en cuanto toques Java, C o C++, y es un recordatorio de que hasta el algoritmo más analizado de la historia escondía un bug durante 60 años.
• Consejo: cuando dudes de tu implementación, prueba sistemáticamente los cuatro casos frontera: lista vacía, un elemento (presente y ausente), objetivo menor que todos, objetivo mayor que todos. Esas cinco pruebas cazan casi todos los off-by-one.

Traza a mano (tabla con izq, der, medio, comparación y acción) la búsqueda del código "TSU" en codigos = ["AVP", "ESN", "HCE", "MVJ", "PDR", "PMA", "POL", "TSU", "UNI"]. ¿Cuántas comparaciones necesita? ¿Y la búsqueda lineal?

RutaBus guarda los kilómetros acumulados de cada expedición de la L1 en una lista ordenada. Escribe cuantas_antes(kms, limite) que devuelva cuántas expediciones llevan estrictamente menos de limite km, en O(log n). Pista: no busques un elemento; busca un punto de corte — puedes hacerlo con tu propia búsqueda binaria o con una llamada a bisect.

Esta versión llega de una revisión de código de RutaBus con dos errores. Encuéntralos y explica qué síntoma produce cada uno (¿resultado incorrecto? ¿bucle infinito?):

Solución 1

3 comparaciones. La lineal habría hecho 8 (es el penúltimo elemento). Con solo 9 elementos la ventaja parece modesta — recuerda de 01-03 que las jerarquías se separan al crecer n.

Solución 2

En una lista ordenada, "cuántos son menores que limite" es exactamente el índice donde limite se insertaría por la izquierda:

A mano sería la búsqueda binaria del "primer índice con kms[i] >= limite". Este patrón — usar la búsqueda binaria para contar en vez de para encontrar — es de los más rentables en la práctica. Error común: usar bisect_right, que contaría también las expediciones con exactamente limite km (el enunciado pedía estrictamente menos).

Solución 3

• Error 1: der = len(lista) con la condición izq <= der. En cuanto el rango se pega al borde derecho, medio puede valer len(lista) y lista[medio] lanza IndexError (por ejemplo, buscando un objetivo mayor que todos los elementos). Corrección: der = len(lista) - 1.
• Error 2: izq = medio sin + 1. Con izq = 4, der = 5, medio = 4; si lista[4] < objetivo, se asigna izq = 4... y el estado no cambia: bucle infinito. Corrección: izq = medio + 1, que además es correcto porque medio ya está descartado.

El síntoma delata al culpable: una excepción de índice apunta a los límites iniciales; un cuelgue apunta a un rango que no encoge.

La deuda está pagada: la búsqueda binaria descarta la mitad de los candidatos en cada comparación gracias al invariante "si está, está en [izq, der]", y eso la hace O(log n) en peor caso y promedio — frente al Θ(n) de buscar_parada —, con O(1) de espacio en su forma iterativa. Hemos visto por qué cada detalle importa (medio + 1 para garantizar la terminación, izq <= der para no perder al último candidato), la variante de primera ocurrencia y el bisect de serie de Python, y hemos catalogado sus trampas históricas, del off-by-one al overflow que vivió 60 años en las bibliotecas estándar. Todo su poder descansa sobre una condición que hemos dado por regalada: que la lista esté ordenada. ¿Y quién la ordena? Ese es exactamente el problema de las tres próximas lecciones. Empezaremos en 04-02 por el algoritmo más humano de todos — el que usas sin saberlo al ordenar cartas o al cuadrar un panel de llegadas a mano —: el ordenamiento por inserción.