La búsqueda binaria
Es posible aprovechar mejor la lista ordenada si somos inteligentes en nuestras comparaciones. En la búsqueda secuencial, cuando comparamos contra el primer ítem, hay a lo sumo n−1 ítems restantes para verificar si el primer ítem no es el valor que estamos buscando. En lugar de buscar secuencialmente en la lista, una búsqueda binaria comenzará examinando el ítem central. Si ese ítem es el que estamos buscando, hemos terminado. Si no es el ítem correcto, podemos utilizar la naturaleza ordenada de la lista para eliminar la mitad de los ítems restantes. Si el ítem que buscamos es mayor que el ítem central, sabemos que toda la mitad inferior de la lista, así como el ítem central, se pueden ignorar de la consideración posterior. El ítem, si es que está en la lista, debe estar en la mitad superior.
Podemos entonces repetir el proceso con la mitad superior. Comenzar en el ítem central y compararlo con el valor que estamos buscando. Una vez más, o lo encontramos o dividimos la lista por la mitad, eliminando por tanto otra gran parte de nuestro espacio de búsqueda posible.
Antes de pasar al análisis, debemos observar que este algoritmo es un gran ejemplo de una estrategia de dividir y conquistar. Dividir y conquistar significa que dividimos el problema en partes más pequeñas, resolvemos dichas partes más pequeñas de alguna manera y luego reensamblamos todo el problema para obtener el resultado. Cuando realizamos una búsqueda binaria en una lista, primero verificamos el ítem central. Si el ítem que estamos buscando es menor que el ítem central, podemos simplemente realizar una búsqueda binaria en la mitad izquierda de la lista original. Del mismo modo, si el ítem es mayor, podemos realizar una búsqueda binaria en la mitad derecha. De cualquier manera, ésta es una llamada recursiva a la función de búsqueda binaria pasándole una lista más pequeña.
defbusquedaBinaria(unaLista, item):if len(unaLista) == 0:
returnFalseelse:
puntoMedio = len(unaLista)//2if unaLista[puntoMedio]==item:
returnTrueelse:
if item<unaLista[puntoMedio]:
return busquedaBinaria(unaLista[:puntoMedio],item)
else:
return busquedaBinaria(unaLista[puntoMedio+1:],item)
listaPrueba = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(busquedaBinaria(listaPrueba, 3))
print(busquedaBinaria(listaPrueba, 13))
Análisis de la búsqueda binaria
Para analizar el algoritmo de búsqueda binaria, necesitamos recordar que cada comparación elimina aproximadamente la mitad de los ítem restantes de la consideración. ¿Cuál es el número máximo de comparaciones que este algoritmo requerirá para examinar la lista completa? Si empezamos con n ítems, alrededor de n/2 ítems se dejarán después de la primera comparación. Después de la segunda comparación, habrá aproximadamente n/4. Después n/8, n/16, y así sucesivamente. ¿Cuántas veces podemos dividir la lista?
<h3>Después de la i-esima comparación el número aproximado de items restantes será de n / (2^i).</h3>Cuando dividimos la lista suficientes veces, terminamos con una lista que tiene un único ítem. Ya sea aquél ítem único el valor que estamos buscando o no lo sea. En todo caso, habremos terminado. El número de comparaciones necesarias para llegar a este punto es i donde n/(2^i)=1. La solución para i nos da ** i=log(n)** . El número máximo de comparaciones es logarítmico con respecto al número de ítems de la lista. Por lo tanto, la búsqueda binaria es O(log(n)).
