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 $2n$‍, 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+1$‍ intentos.

Echemos un vistazo al 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 dividimos repetidamente a la mitad, empezando en $n$‍, hasta obtener el valor de 1, más uno". Pero esa es una manera inconveniente de escribirlo.

Afortunadamente, hay una función matemática que significa lo mismo que el número de veces que dividimos repetidamente a la mitad, empezando en $n$‍, hasta obtener el valor de 1: el logaritmo base 2 de $n$‍. Eso suele escribirse como ${\log }_{2}n$‍, pero quizá también lo hayas visto escrito como $\lg n$‍ en escritos de ciencias de las computación. (¿Quieres repasar logaritmos? Aprende más aquí).

Aquí está una tabla que muestra los logaritmos base 2 de varios valores de $n$‍:

Podemos ver estas 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 ${\log }_{2}n=x$‍, entonces $n=2^x$‍. Por ejemplo, como ${\log }_{2}128=7$‍, sabemos que $2^7=128$‍.

Eso facilita calcular el tiempo de ejecución de un algoritmo de una búsqueda binaria en una $n$‍ que es exactamente una potencia de 2. Si $n$‍ es 128, la búsqueda binaria a lo más requerirá de 8 (${\log }_{2}128+1$‍) intentos.

¿Qué pasa si $n$‍ no es una potencia de 2? En ese caso podemos fijarnos en la potencia de 2 que sea más cercana por abajo. Para un arreglo cuya longitud sea de 1000, la potencia de 2 más cercana por abajo es 512, que es igual a $2^9$‍. Así que podemos estimar que ${\log }_{2}1000$‍ es un número mayor que 9 y menor que 10, o usar una calculadora para ver que es aproximadamente 9.97. Sumarle uno a eso nos da aproximadamente 10.97. En caso de obtener un número decimal, redondeamos hacia abajo para encontrar el número real de intentos. Por lo tanto, para un arreglo de 1000 elementos, una búsqueda binaria requeriría a lo más 10 intentos.

Para el catálogo estelar Tycho-2 con 2,539,913 estrellas, la potencia de 2 más cercana por abajo es $2^{21}$‍ (que es 2,097,152), así que a lo más necesitaríamos 22 intentos. ¡Mucho mejor que una búsqueda lineal!

Compara $n$‍ contra ${\log }_{2}n$‍ 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.