Tiempo de ejecución de la búsqueda binaria

Sabemos que una búsqueda lineal en un arreglo de n elementos puede tomar hasta n intentos. Probablemente ya tengas una idea intuitiva de que la búsqueda binaria hace menos intentos que una búsqueda lineal. Incluso puede que hayas percibido que la diferencia entre el número de intentos en el peor caso de una búsqueda lineal y una búsqueda binaria se vuelve más notable a medida que la longitud del arreglo aumenta. Veamos cómo analizar el número máximo de intentos que hace una búsqueda binaria.
La idea clave es que cuando una búsqueda binaria hace un intento incorrecto, la porción del arreglo que contiene los intentos razonables se reduce por lo menos a la mitad. Si la porción razonable tenía 32 elementos, entonces un intento incorrecto la reduce para que tenga a lo más 16. La búsqueda binaria reduce el tamaño de la porción razonable a la mitad después de cada intento incorrecto.
Si empezamos con un arreglo de longitud 8, los intentos incorrectos reducen el tamaño de la porción razonable a 4, luego a 2 y luego a 1. Una vez que la porción razonable contiene solo un elemento, no ocurren más intentos; el intento para la porción de 1 elemento es correcta o incorrecta, y ya terminamos. Así que con un arreglo de longitud 8, la búsqueda binaria necesita a lo más cuatro intentos.
¿Qué crees que pasaría con un arreglo de 16 elementos? Si dijiste que el primer intento eliminaría al menos 8 elementos, de modo que a lo más quedarán 8, le estás entendiendo. Así que con 16 elementos, necesitamos a lo más cinco intentos.
A estas alturas probablemente ya estás viendo el patrón. Cada vez que duplicamos el tamaño del arreglo, necesitamos a lo más un intento más. Supón que necesitamos a lo más m intentos para un arreglo de longitud n. Entonces, para un arreglo de longitud 2, n, el primer intento corta la porción razonable del arreglo a un tamaño n, y a lo más en m intentos terminamos, dándonos un total de a lo más m, plus, 1 intentos.
Vamos a ver el caso general de un arreglo de longitud n. Podemos expresar el número de intentos, en el peor caso, como "el número de veces que podemos repetidamente reducir a la mitad, empezando en n, hasta que obtengamos el valor 1, más uno". Pero eso es inconveniente para escribir. Afortunadamente, hay una función matemática que significa lo mismo que el número de veces que repetidamente reducimos a la mitad, empezando en n, hasta que obtenemos el valor de 1: el logaritmo base 2 de n. Lo escribimos como lgn \lg n . (Puedes aprender más sobre logaritmos aquí).
Aquí está una tabla que muestra los logaritmos base 2 de varios valores de n:
nlgn \lg n
10
21
42
83
164
325
646
1287
2568
5129
102410
1,048,57620
2,097,15221
Podemos ver esta misma tabla como una gráfica:
Un acercamiento a valores más pequeños de n:
La función logaritmo crece muy lentamente. Los logaritmos son los inversos de las exponenciales, que crecen muy rápidamente, de modo que si lgn=x \lg n = x , entonces n, equals, 2, start superscript, x, end superscript. Por ejemplo, como lg128=7 \lg 128 = 7 , sabemos que 2, start superscript, 7, end superscript, equals, 128.
Cuando n no es una potencia de 2, simplemente podemos ir a la siguiente potencia de 2. Para un arreglo cuya longitud es 1000, la siguiente potencia de 2 es 1024, que es igual a 2, start superscript, 10, end superscript. Por lo tanto, para un arreglo de 1000 elementos, la búsqueda binaria requeriría a lo más 11 (10 + 1) intentos. Para el catálogo estelar Tycho-2 con 2,539,913 estrellas, la siguiente potencia de 2 es 2, start superscript, 22, end superscript (que es 4,194,304), y necesitaríamos a lo más 23 intentos. ¡Mucho mejor que la búsqueda lineal! Compáralas a continuación:
En la siguiente lección, veremos cómo los computólogos caracterizan los tiempos de ejecución de la búsqueda lineal y la búsqueda binaria, al usar una notación que extrae la parte más importante del tiempo de ejecución y descarta las partes menos importantes.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.