Lección 8: Búsqueda binaria

Juguemos a adivinar: pensé un número entre 1 y 100, y en cada intento digo 'muy alto' o 'muy bajo'. La jugada inteligente: adivinar el medio cada vez y descartar la mitad de las opciones. Eso es exactamente la 'búsqueda binaria': un algoritmo que encuentra un valor en una lista ordenada, reduciendo

La búsqueda binaria es como buscar una palabra en un diccionario grueso: no lees página por página desde el principio. Abres por la mitad, y si tu palabra viene después en el alfabeto, descartas toda la primera mitad de una vez. Cada vistazo corta a la mitad lo que queda por buscar.

búsqueda binaria: Un algoritmo de búsqueda sobre un array ordenado que en cada paso revisa el medio y descarta la mitad que no puede contener el objetivo: O(log n).
tiempo logarítmico: O(log n): el número de pasos crece muy lentamente; cada vez que n se duplica se agrega solo un paso más, porque el espacio de búsqueda se reduce a la mitad cada vez.
espacio de búsqueda: El rango de índices [low, high] que todavía puede contener el objetivo; la búsqueda binaria lo reduce a la mitad en cada iteración.