Búsqueda binaria

Mira el centro, descarta la mitad que no puede contenerlo. O(log n) sobre datos ordenados.

Cada sondeo parte a la mitad los candidatos

• 1000 elementos → ~10 sondeos
• 1,000,000 → ~20
• 1,000,000,000 → ~30
• lower_bound / upper_bound: dónde iría un valor (más útil)

Mira colapsar la ventana

21 elementos, objetivo 30 → encontrado en 5 sondeos. La ventana azul se parte a la mitad en cada paso.

O(log n) vs O(n)

El recorrido lineal sube y se sale de la gráfica. Binaria/bisect se quedan planas.

Famosa por sus bugs

• Límites con error de uno-por-uno · overflow en (lo+hi)/2 (vivió años en el JDK)
• Usa una ventana semiabierta [lo, hi) de forma consistente
• Exige entrada ordenada, en silencio
• O de plano llama a bisect

Para llevar

Busca en datos ordenados con un logaritmo, nunca con un recorrido. Se generaliza a "búsqueda binaria sobre la respuesta". Sigue: quickselect.