8.3. Búsqueda lineal

Diseñamos una solución: Podemos comparar uno a uno los elementos de la lista con el valor de x, y retornar el valor de la posición donde lo encontramos en caso de encontrarlo.

Si llegamos al final de la lista sin haber salido antes de la función es porque el valor de x no está en la lista, y en ese caso retornamos −1.

En esta solución necesitamos una variable i que cuente en cada momento en qué posición de la lista estamos parados. Esta variable se inicializa en 0 antes de entrar en el ciclo y se incrementa en 1 en cada paso.

El programa nos queda entonces como se muestra en el Código 8.2.

# Código 8.2 busqueda_lineal.py: Función de búsqueda lineal

#!/usr/bin/env python
# encoding: latin1

def busqueda_lineal(lista, x):
    """ Búsqueda lineal.
    Si x está en lista devuelve su posición en lista, de lo
    contrario devuelve -1.
    """

# Estrategia: se recorren uno a uno los elementos de la lista
# y se los compara con el valor x buscado.
i=0 # i tiene la posición actual en la lista, comienza en 0

# el ciclo for recorre todos los elementos de lista:
for z in lista:
    # estamos en la posicion i, z contiene el valor de lista[i]

    # si z es igual a x, devuelve i
    if z == x:
        return i

    # si z es distinto de x, incrementa i, y continúa el ciclo
    i=i+1

# si salió del ciclo sin haber encontrado el valor, devuelve -1
return -1

Y ahora lo probamos:

>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 44)
-1
>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 3)
3
>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 0)
4
>>> busqueda_lineal([], 0)
-1
>>>

8.3.1. ¿Cuántas comparaciones hace este programa?

Volvemos a preguntarnos lo mismo que en la sección anterior, pero con el nuevo programa: ¿cuánto esfuerzo computacional requiere este programa?, ¿cuántas veces compara el valor que buscamos con los datos de la lista? Ahora podemos analizar el texto de busqueda_lineal:

• La línea 16 del código es un ciclo que recorre uno a uno los elementos de la lista, y en el cuerpo de ese ciclo, en la línea 20 se compara cada elemento con el valor buscado. En el caso de encontrarlo (línea 21) se devuelve la posición.
• Si el valor no está en la lista se recorrerá la lista entera, haciendo una comparación por elemento.

O sea que si el valor está en la posición p de la lista se hacen p comparaciones, y si el valor no está se hacen tantas comparaciones como elementos tenga la lista.

Nuestra hipótesis es: Si la lista crece, la cantidad de comparaciones para encontrar un valor arbitrario crecerá en forma proporcional al tamaño de la lista.

Diremos que este algoritmo tiene un comportamiento proporcional a la longitud de la lista involucrada, o que es un algoritmo lineal.

En la próxima sección veremos cómo probar esta hipótesis.