¿Podemos hacer algo mejor? Trataremos de aprovechar el hecho de que la lista está ordenada y vamos a hacer algo distinto: nuestro espacio de búsqueda se irá achicando a segmentos cada vez menores de la lista original. La idea es descartar segmentos de la lista donde el valor seguro que no puede estar:
- Consideramos como segmento inicial de búsqueda a la lista completa.
- Analizamos el punto medio del segmento (el valor central), si es el valor buscado, devolvemos el índice del punto medio.
- Si el valor central es mayor al buscado, podemos descartar el segmento que está desde el punto medio hacia la a derecha.
- Si el valor central es menor al buscado, podemos descartar el segmento que está desde el punto medio hacia la izquierda.
- Una vez descartado el segmento que no nos interesa, volvemos a analizar el segmento restante, de la misma forma.
- Si en algún momento el segmento a analizar tiene longitud
0
o negativa significa que el valor buscado no se encuentra en la lista.
Para señalar la porción del segmento que se está analizando a cada paso,
utilizaremos dos variables (izq
y der
) que contienen la posición de
inicio y la posición de fin del segmento que se está considerando. De la
misma manera usaremos la varible medio
para contener la posición del
punto medio del segmento.
En el gráfico que se incluye a continuación, vemos qué pasa cuando se
busca el valor 18
en la lista [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23]
.
Como no se encontró al valor buscado, devuelve −1
. En el Código 8.3 mostramos una posible implementación de este algoritmo.
A continuación varias ejecuciones de prueba:
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 0
DEBUG: izq: 0 der: 2 medio: 1
DEBUG: izq: 0 der: 0 medio: 0
Resultado: -1
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 1
DEBUG: izq: 0 der: 2 medio: 1
DEBUG: izq: 0 der: 0 medio: 0
Y este es el código fuente:
# Código 8.3: busqueda_binaria.py: Función de búsqueda binaria
#!/usr/bin/env python
# encoding: latin1
def busqueda_binaria(lista, x):
"""Búsqueda binaria
Precondición: lista está ordenada
Devuelve -1 si x no está en lista;
Devuelve p tal que lista[p] == x, si x está en lista
"""
# Busca en toda la lista dividiéndola en segmentos y considerando
# a la lista completa como el segmento que empieza en 0 y termina
# en len(lista) - 1.
izq = 0 # izq guarda el índice inicio del segmento
der = len(lista) -1 # der guarda el índice fin del segmento
# un segmento es vacío cuando izq > der:
while izq <= der:
# el punto medio del segmento
medio = (izq+der)/2
print "DEBUG:", "izq:", izq, "der:", der, "medio:", medio
# si el medio es igual al valor buscado, lo devuelve
if lista[medio] == x:
return medio
# si el valor del punto medio es mayor que x, sigue buscando
# en el segmento de la izquierda: [izq, medio-1], descartando la
# derecha
elif lista[medio] > x:
der = medio-1
# sino, sigue buscando en el segmento de la derecha:
# [medio+1, der], descartando la izquierda
else:
izq = medio+1
# si no salió del ciclo, vuelve a iterar con el nuevo segmento
# salió del ciclo de manera no exitosa: el valor no fue encontrado
return -1
# Código para probar la búsqueda binaria
def main():
lista = input ("Dame una lista ordenada ([[]] para terminar): ")
while lista != [[]]:
x = input("¿Valor buscado?: ")
resultado = busqueda_binaria(lista, x)
print "Resultado:", resultado
lista = input ("Dame una lista ordenada ([[]] para terminar): ")
main()
Resultado: 0
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 2
DEBUG: izq: 0 der: 2 medio: 1
DEBUG: izq: 0 der: 0 medio: 0
Resultado: -1
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 3
DEBUG: izq: 0 der: 2 medio: 1
Resultado: 1
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 5
DEBUG: izq: 0 der: 2 medio: 1
DEBUG: izq: 2 der: 2 medio: 2
Resultado: 2
Dame una lista ordenada ([[]] para terminar): [1, 3, 5]
¿Valor buscado?: 6
DEBUG: izq: 0 der: 2 medio: 1
DEBUG: izq: 2 der: 2 medio: 2
Resultado: -1
Dame una lista ordenada ([[]] para terminar): []
¿Valor buscado?: 0
Resultado: -1
Dame una lista ordenada ([[]] para terminar): [1]
¿Valor buscado?: 1
DEBUG: izq: 0 der: 0 medio: 0
Resultado: 0
Dame una lista ordenada ([[]] para terminar): [1]
¿Valor buscado?: 3
DEBUG: izq: 0 der: 0 medio: 0
Resultado: -1
Dame una lista ordenada ([[]] para terminar): [[]]
8.5.1. ¿Cuántas comparaciones hace este programa?
Para responder esto pensemos en el peor caso, es decir, que se descartaron varias veces partes del segmento para finalmente llegar a un segmento vacío y porque el valor buscado no se encontraba en la lista.
En cada paso el segmento se divide por la mitad y se desecha una de esas
mitades, y en cada paso se hace una comparación con el valor buscado.
Por lo tanto, la cantidad de comparaciones que hacen con el valor
buscado es aproximadamente igual a la cantidad de pasos necesarios para
llegar a un segmento de tamaño 1. Veamos el caso más sencillo para
razonar, y supongamos que la longitud de la lista es una potencia de 2,
es decir len(lista)= 2^k
:
- Luego del primer paso, el segmento a tratar es de tamaño
2^k
. - Luego del segundo paso, el segmento a tratar es de tamaño
2^(k−1)
. - Luego del tercer paso, el segmento a tratar es de tamaño
2^(k−2)
. - ...
- Luego del paso
k
, el segmento a tratar es de tamaño2^(k−k) = 1
.
Por lo tanto este programa hace aproximadamente k comparaciones con el
valor buscado cuando len(lista)= 2^k
. Pero si despejamos k
de la
ecuación anterior, podemos ver que este programa realiza aproximadamente
log2(len(lista))
comparaciones.
Cuando len(lista)
no es una potencia de 2 el razonamiento es menos
prolijo, pero también vale que este programa realiza aproximadamente
log2(len(lista))
comparaciones.
Vemos entonces que si lista es una lista
ordenada, la búsqueda binaria
es muchísimo más eficiente que la búsqueda lineal (por ejemplo, dado
que 2^20
es aproximadamente 1.000.000, si lista
tiene 1.000.000 de
elementos, la búsqueda lineal sobre lista será proporcional a 1.000.000,
y en promedio hará unas 500.000 comparaciones, mientras que la búsqueda
binaria hará como máximo 20 comparaciones).