Búsqueda lineal y búsqueda binaria

Una búsqueda es encontrar un dato dentro de una lista, como un nombre en tu agenda. Con la búsqueda lineal y la búsqueda binaria encuentras un dato mirando muy pocos elementos.

Piensa en la lista de bicicletas alquiladas cada día de un año: 365 números. Buscas un día concreto. ¿Cuántos tienes que mirar?

Imagina que buscas tu nombre en una lista de clase sin ordenar. Empiezas por el primero y sigues hasta encontrarlo.

Eso es la búsqueda lineal. Funciona con cualquier lista, ordenada o no. En el peor caso, el dato está el último o no está, y miras los 365 elementos.

# Devuelve el índice del dato, o -1 si no está.
def linear_search(items, target):
    for index in range(len(items)):
        if items[index] == target:
            return index
    return -1

hires = [137, 212, 173, 327, 204, 98, 251]
print(linear_search(hires, 327))
print(linear_search(hires, 500))

docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(len(h), h[:5])"

docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(max(h), h.index(max(h)) + 1)"

El primer Run imprime 365 [137, 212, 173, 327, 204]: hay 365 días y estos son los cinco primeros.

El segundo imprime 487 173. El máximo, 487 alquileres, está en el índice 172. La búsqueda lineal necesitó 173 comparaciones para llegar hasta él.

Si la lista está ordenada, hay un atajo. Miras el elemento del medio.

Si es menor que el dato, todo lo de su izquierda es menor también, así que lo descartas. Si es mayor, descartas la derecha. Repites con la mitad que queda.

Es como adivinar un número del 1 al 100 cuando te dicen "más alto" o "más bajo".

# La lista tiene que estar ordenada.
def binary_search(items, target):
    low = 0
    high = len(items) - 1
    steps = 0
    while low <= high:
        middle = (low + high) // 2
        steps = steps + 1
        if items[middle] == target:
            return middle, steps
        if items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1, steps

ordered = [5, 12, 18, 25, 31, 40, 47, 58, 66]
print(binary_search(ordered, 58))
print(binary_search(ordered, 20))

docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(h == sorted(h), sorted(h)[:5])"

El Run imprime False [41, 61, 79, 94, 101]. Los alquileres están en el orden de los días, no de menor a mayor, y los cinco más bajos de todo el año son esos.

Para usar la búsqueda binaria aquí, primero hay que ordenar la lista. Ordenar tiene su propio coste, y lo verás en la próxima lección.

Cada paso deja la mitad de los elementos. Con 16 elementos quedan 8, luego 4, luego 2 y luego 1. Son 5 pasos como máximo.

Una lista diez veces más larga no necesita diez veces más pasos. Solo necesita unos pocos más.

docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(len(h).bit_length())"

El Run imprime 9. El número 365 se escribe con nueve cifras en binario, y ese es justo el máximo de pasos de la búsqueda binaria.

Mira la tabla: la búsqueda lineal crece con la lista, y la binaria casi no cambia.

En el cuaderno, ordena la lista con sorted y busca un valor con tu función. Después prueba %timeit con la búsqueda lineal y con bisect_left del módulo bisect.

Apunta lo que ves. El tiempo cambia de una máquina a otra y de una vez a otra. Los pasos no cambian nunca: por eso los contamos.