Capítulo 8. Algoritmos de búsqueda

8.1. El problema de la búsqueda

Presentamos ahora uno de los problemas más clásicos de la computación, el problema de la búsqueda, que se puede enunciar de la siguiente manera:

Problema: Dada una lista xs y un valor x devolver el índice de x en xs si x está en xs, y −1 si x no está en xs`.

Alicia Hacker afirma que este problema tiene una solución muy sencilla en Python: se puede usar directamente la poderosa función index() de lista.

Probamos esa solución para ver qué pasa:

>>> [1,3,5,7].index(5)
2
>>> [1,3,5,7].index(20)
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
ValueError: list.index(x): x not in list

Vemos que usar la función index() resuelve nuestro problema si el valor buscado está en la lista, pero si el valor no está no sólo no devuelve un −1, sino que se produce un error.

El problema es que para poder aplicar la función index() debemos estar seguros de que el valor está en la lista, y para averiguar eso Python nos provee del operador in:

>>> 5 in [1,3,5,7]
True
>>> 20 in [1, 3, 5, 7]
False

O sea que si llamamos a la función index() sólo cuando el resultado de in es verdadero, y devolvemos −1 cuando el resultado de in es falso, estaremos resolviendo el problema planteado usando sólo funciones provistas por Python. La solución se muestra en el código 8.1.

Probamos la función busqueda_con_index():

>>> busqueda_con_index([1,   4,   54,   3,   0,   -1],   1)
0
>>> busqueda_con_index([1,   4,   54,   3,   0,   -1],   -1)
5

# busqueda_con_index.py: Busca utilizando index e in provistos por Python

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

def busqueda_con_index(xs, x):
    """Busca un elemento x en una lista xs
    si x está en xs devuelve xs.index(x)
    de lo contrario devuelve -1
    """

    if x in xs:
        return(xs.index(x))
    else:
        return(-1)

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

8.1.1. ¿Cuántas comparaciones hace este programa?

La pregunta del título se refiere a ¿cuánto esfuerzo computacional requiere este programa?, ¿cuántas veces compara el valor que buscamos con los datos de la lista? No lo sabemos porque no sabemos cómo están implementadas las funciones in e index(). La pregunta queda planteada por ahora pero daremos un método para averiguarlo más adelante en esta unidad.