8.5. Búsqueda binaria

¿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:

1. Consideramos como segmento inicial de búsqueda a la lista completa.
2. Analizamos el punto medio del segmento (el valor central), si es el valor buscado, devolvemos el índice del punto medio.
3. Si el valor central es mayor al buscado, podemos descartar el segmento que está desde el punto medio hacia la a derecha.
4. Si el valor central es menor al buscado, podemos descartar el segmento que está desde el punto medio hacia la izquierda.
5. Una vez descartado el segmento que no nos interesa, volvemos a analizar el segmento restante, de la misma forma.
6. 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].

Figura 8.1 Cómo funciona la búsqueda de un elemento dentro del array

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ño 2^(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).