3.3 Búsqueda de elementos en una lista

Uno de los usos principales para las listas es que permiten guardar mucha información, para poder acceder luego a la misma. Este acceso puede ser general (quiero acceder a todos los elementos de una lista) o específico (quiero acceder a un dato en particular).
En el primer caso, sólo hay que recorrer la lista entera con ciclo. Vamos a ver ahora cómo acceder a un dato específico en una lista, mediante algoritmos de búsqueda.
Para ello, vamos a crear una función Buscar, que deberá recorrer la lista viendo si cada elemento de la misma coincide con el dato a buscar. Si el elemento coincide, la función debe devolver la posición de la lista en la que está, si no coincide debe pasar a comparar el siguiente elemento. Si llego al final de la lista sin haber encontrado un elemento igual al dato, significa que no hay un elemento igual en la lista. En este caso, la función deberá devolver -1 para que el programa sepa que no se encontró el dato.

def buscar(L, elem):
    for i in range(0, len(L)):
        if L[i]==elem:
                   return i
    return -1

La función recibe como parámetros la lista y el dato a buscar. Devuelve un int con la posición en que encontró el dato (o -1 si no lo encuentra).

Un programa que use la función, podría ser por ejemplo:


import random


def buscar(L, elem):
    for i in range(0, len(L)):
        if L[i]==elem:
                   return i
    return -1

def CrearLista():
    n=5
    lista = []
    for i in range(0,n):
        lista.append(random.randint(0, 100))
    print( "Lista inicial:",lista)
## Ordenamiento
    n=int(input("Ingrese un elemento a buscar:"))
    x = buscar(lista,n)
    print("Está en la posicion:",x)

CrearLista()



Primero se carga la lista con valores aleatorios enteros. Luego se le pide al usuario que ingrese un número, y se llama a la función buscar, pasándole ese número y la lista.
Si el valor que devuelve la función es -1, significa que el elemento no estaba en la lista, en caso contrario, devuelve la posición en la que está el número a buscar.

Este método de búsqueda, no es muy eficiente, si el elemento no está en la lista, tiene que comparar todos los elementos de la misma para darse cuenta. Si el elemento está en la lista, depende de su posición: si es el primero, lo encuentra en una comparación; pero si el elemento es el último, tardará N comparaciones en encontrarlo. Si N es la cantidad de elementos de la lista, se tardará en promedio N/2 comparaciones en encontrar el elemento.

Si queremos hacer la búsqueda más rápidamente, necesitamos que la lista esté ordenada. Así, en vez de empezar a comparar desde el principio, comparamos el dato con el elemento que está en la mitad de la lista. Si el dato es menor al elemento medio de la lista, ya podemos descartar toda la mitad superior de la misma. Si el elemento es mayor, descartamos la primera mitad de la lista. Luego podemos llamar recursivamente a la función para que busque en la media lista que le queda.
Así hasta que el elemento medio de la lista sea igual al dato, o hasta que no quede sub-lista donde buscarlo. Esta búsqueda es mucho más rápida, ya que cada comparación permite descartar la mitad de los elementos de la lista. Se puede comprobar que la cantidad de búsquedas a realizar es aproximadamente log2(n) / 2, lo que es mucho más rápido que n/2, y esa diferencia aumenta más cuanto más grande sea n.


def buscarBinario(L, desde, hasta, elem):
    if desde > hasta:
        return -1
    mitad = int((desde+hasta) /2)
    if L[mitad]==elem:
        return mitad
    elif L[mitad] < elem:
        return buscarBinario(L,mitad+1,hasta,elem)
    else:
        return buscarBinario(L,desde,mitad-1,elem)

def CrearLista():
    n=5
    lista = []
    for i in range(0,n):
        lista.append(random.randint(0, 100))
    print( "Lista inicial:",lista)
    lista.sort()
    print( "Lista ordenada:",lista)
    n=int(input("Ingrese un elemento a buscar:"))
    x = buscarBinario(lista,0,len(lista)-1,n)
    print("Está en la posicion:",x)
CrearLista()

La función tiene cuatro salidas posibles:
 - Si los límites "desde" y "hasta" están cruzados (desde > hasta) significa que fui achicando el rango en el que buscar tanto que ya no me quedó lista donde buscar. Por lo tanto, el dato a buscar no está en la lista y devuelvo -1.
- Si el dato a buscar coincide con el elemento que está en la mitad del rango en el que busco, devuelvo la posición de esa mitad y termina la búsqueda.
- Si el dato a buscar es mayor que el elemento que está en la mitad de la lista, debo buscar en el rango (mitad+1; hasta) de la lista.
- Si el dato a buscar es menor que el elemento que está en la mitad de la lista, debo buscar en el rango (desde; mitad-1) de la lista.



Las funciones que hemos visto aquí para buscar elementos en una lista pueden fácilmente escribirse en cualquier lenguaje de programación.
Al igual que para ordenar, el Python ya tiene un método programado para buscar elementos en una lista, y es el método index()

list.index(x[, start[, end]])

Index devuelve la posición del elemento x en la lista list. Adicionalmente, se puede acotar el rango de búsqueda con los parámetros start y end. Si no se encuentra el elemento en la lista, devuelve un error.

Más información acerca de métodos de listas en el link:  https://docs.python.org/3.6/tutorial/datastructures.html#more-on-lists