Uno de los problemas más comunes es la búsqueda, que es el proceso algorítmico de encontrar un elemento particular en una colección de elementos. Una búsqueda normalmente devuelve True o False según el ítem esté o no presente, respectivamente. En ocasiones, el algoritmo se puede modificar para devolver la posición donde se encuentre el ítem. Para nuestros propósitos, simplemente nos ocuparemos de la pregunta sobre la membresía.
En Python, hay una manera muy fácil de preguntar si un ítem está en una lista de elementos. Utilizamos el operador in.
>>> 15 in [3,5,2,4,1]
False
>>> 3 in [3,5,2,4,1]
True
>>>
A pesar de que esto es fácil de escribir, un proceso subyacente debe llevarse a cabo para responder a la pregunta. Resulta que hay muchas maneras diferentes de buscar el ítem. Lo que nos interesa aquí es cómo funcionan estos algoritmos y compararlos entre sí.
La búsqueda secuencial
Cuando los ítems de datos se almacenan en una colección, por ejemplo en una lista, decimos que tienen una relación lineal o secuencial. Cada ítem de datos se almacena en una posición relativa a los demás. En las listas de Python, estas posiciones relativas son los valores de los índices de los ítems individuales. Dado que estos valores de los índices están ordenados, es posible para nosotros visitarlos en secuencia. Este proceso da lugar a nuestra primera técnica de búsqueda, la búsqueda secuencial.
La Figura 1 muestra cómo funciona esta búsqueda. Comenzando en el primer ítem de la lista, simplemente nos trasladamos de un ítem a otro, siguiendo el orden secuencial subyacente hasta que encontremos lo que buscamos o nos quedemos sin ítems. Si nos quedamos sin ítems, hemos descubierto que el ítem que estábamos buscando no estaba presente.
La implementación en Python para este algoritmo implica una función, necesita la lista y el elemento que estamos buscando y devuelve un valor booleano (true o false) que indica si el elemento está o no presente. La variable booleana encontrado se inicializa en False y se le asigna el valor True si descubrimos el ítem en la lista.
Realiza el ejercicio.
La búsqueda binaria
Es posible aprovechar mejor la lista ordenada si somos inteligentes en nuestras comparaciones. En la búsqueda secuencial, cuando comparamos contra el primer ítem, hay a lo sumo n−1n−1 ítems restantes para verificar si el primer ítem no es el valor que estamos buscando. En lugar de buscar secuencialmente en la lista, una búsqueda binaria comenzará examinando el ítem central. Si ese ítem es el que estamos buscando, hemos terminado. Si no es el ítem correcto, podemos utilizar la naturaleza ordenada de la lista para eliminar la mitad de los ítems restantes. Si el ítem que buscamos es mayor que el ítem central, sabemos que toda la mitad inferior de la lista, así como el ítem central, se pueden ignorar de la consideración posterior. El ítem, si es que está en la lista, debe estar en la mitad superior.
Podemos entonces repetir el proceso con la mitad superior. Comenzar en el ítem central y compararlo con el valor que estamos buscando. Una vez más, o lo encontramos o dividimos la lista por la mitad, eliminando por tanto otra gran parte de nuestro espacio de búsqueda posible. La Figura 3 muestra cómo este algoritmo puede encontrar rápidamente el valor 54.
