Análisis de complejidad temporal sobre Binary Search | CourseIt Blog
logo courseit

Análisis de complejidad temporal sobre Binary Search

32

Binary search es un algoritmo de búsqueda que aplica a listas ordenadas. La estrategia es recursivamente partir el array a la mitad y buscar en que mitad esta el numero que buscamos hasta encontrarlo o detectar que no se encuentra en nuestra lista.

Por ejemplo, si buscamos el numero 9 en la lista 1,2,3,4,5,6,7,8,9,10,11,12 el proceso sería:

  1. Buscamos el valor medio aproximando hacia abajo (6) y validamos de que lado esta el número que buscamos (9). En base a eso cortamos el array.
  2. Partiendo desde nuestro nuevo array (6,7,8,9,10,11,12) volvemos a aplicar el punto uno. En esta iteración encontramos el número buscado (9) ya que es el valor medio del array

La complejidad temporal del algoritmo Binary Search es O(log n). Ahora bien, ¿Cómo llegamos a esto? Bueno, para hacerlo vamos a tener que saber algunos conceptos de análisis matemático.

Arranquemos planteando que nuestro algoritmo termina luego de X cantidad de iteraciones. En el caso de nuestro ejemplo termina luego de 2 iteraciones pero como los algoritmos resuelven problemas de manera genérica, ese numero va a ser una incógnita para nosotros.

En base a eso podemos decir que en la primera iteración la longitud de nuestro array es igual a n

Longitud = n

En la segunda iteración la longitud de nuestro array es n/2 ya que lo partimos a la mitad

Longitud = n/2

Y si tuviésemos una tercera iteración sería la mitad de la mitad, lo que podríamos expresar como n/(2^x) donde n es la longitud del array y x la cantidad de iteraciones.

Longitud = n(2^x)

Por último, otra cosa que tambien sabemos es que si continuamos aplicando binary search, eventualmente nuestro array termina siendo de un unico elemento (podes probar esto aplicando el algoritmo para encontrar el numero 12 en el siguiente array: 1,2,3,4,5,6,7,8,9,10,11,12)

Teniendo en cuenta esto, podemos asegurar que:

Longitud = n(2^x) = 1

Por lo que si hacemos pasaje de términos nos quedaría

n = 1 * 2^x
n = 2^x

Ahora si aplicamos logaritmo en ambos lados de la igualdad obtenemos

log2(n) = log2(2^x)

Y por las propiedades de los logaritmos podemos pasar la potencia que esta dentro del logaritmo como multiplicador del mismo

log2(n) = x * log2(2)

Por último aplicamos la propiedad de los logaritmos que nos dicen que loga (a) = 1

log2(n) = x * 1

x = log2(n)

Conclusión: La complejidad temporal del Binary Search es log n. Por fortuna para todas las personas que lograron llegar hasta acá, este tipo de análisis no son para nada comunes en entrevistas técnicas por lo que todo el contenido que les compartí es meramente informativo para quienes tengan curiosidad.