29. Búsqueda de datos¶

En este apartado vamos a estudiar cómo buscar datos dentro de una lista. Existen numerosas funciones y métodos de Python para conseguirlo, pero en esta unidad se van a estudiar los algoritmos de búsqueda sin su ayuda para poder aprender cómo funcionan estos algoritmos internamente.

Búsqueda lineal de datos¶

El algoritmo más sencillo para buscar un dato en una lista consiste en ir recorriendo todos los elementos de la lista, uno a uno, hasta encontrar aquel que estamos buscando.

En este caso vamos a programar una búsqueda lineal del menor elemento de una lista de datos.

Una variable guardará la posición del menor elemento encontrado hasta el momento e iremos actualizando esta posición a medida que vayamos encontrando otros elementos menores:

def busca_menor(lista):
    """Busca el elemento menor de una lista"""

    # El elemento menor será el primero, para empezar
    menor = 0

    for i in range(len(lista)):
        if lista[i] < lista[menor]:
            menor = i

    return menor


lista = [
    75, 13, 92, 99, 19, 33, 40, 42, 85, 17,
    44, 63,  8, 87, 72, 51, 46, 87, 35, 53
    ]

menor = busca_menor(lista)

print(f'El menor elemento está en la posición {menor}')
print(f'Su valor es {lista[menor]}')

El resultado es el siguiente:

El menor elemento está en la posición 12
Su valor es 8

Ejercicios¶

Escribe un programa con una función que busque el elemento mayor de una lista. Llama a esa función con la lista de números anterior para comprobar que el resultado es el elemento 3 que vale 99.

Escribe una función que devuelva la posición del último elemento par de una lista. Si no existe ningún número par, el resultado devuelto debe ser la constante None para indicar que no existe ninguno.

Llama a la función con la lista de números anterior para comprobar que el resultado es la posición 16, número 46.

Pista:

def ultimo_par(lista):
    ultimo = None

    for i in range(len(lista)):
        if ...

    return ultimo

lista = [
    75, 13, 92, 99, 19, 33, 40, 42, 85, 17,
    44, 63,  8, 87, 72, 51, 46, 87, 35, 53
    ]
ultimo = ultimo_par(lista)
print( ... )
print( ... )

Resultado:

El último elemento par está en la posición 16
Su valor es 46

Escribe una función que devuelva la posición del primer elemento impar de una lista. Si no existe ningún número impar, el resultado devuelto debe ser la constante None para indicar que no existe ninguno.

Llama a la función con la lista de números anterior para comprobar que el resultado es la posición 0, número 75.

Resultado:
```
El primer elemento impar está en la posición 0
Su valor es 75
```

Escribe una función que cuente las veces que se encuentra un elemento en una lista. Llama a esa función para calcular cuántas veces aparece el elemento 5 en una lista de notas.

Pista:

def buscar(lista, numero):
    contador = 0
    for i in lista:
        if ...


notas = [
    8, 3, 6, 6, 2, 9, 4, 3, 5, 9,
    3, 1, 2, 5, 8, 4, 3, 10, 4, 6
    ]

cantidad = buscar(notas, 5)
print(f'Hay un total de {cantidad} notas iguales a 5')

Modifica el programa anterior con un bucle que busque cuántas veces aparecen todas las notas desde el 0 hasta el 10.

Modifica el programa de búsqueda del elemento menor de una lista. Añade al programa otra función que vaya buscando una y otra vez el elemento menor, que lo imprima en pantalla y que lo borre de la lista con la función del(). El resultado final debe ser que imprima todos los elementos de la lista ordenados de menor a mayor.

Pista:

def busca_menor(lista):
    """Busca el elemento menor de una lista"""

    menor = 0

    for i in range(len(lista)):
        if lista[i] < lista[menor]:
            menor = i

    return menor


def lista_menores(lista):
    ...
    ...
    ...


lista = [
    75, 13, 92, 99, 19, 33, 40, 42, 85, 17,
    44, 63,  8, 87, 72, 51, 46, 87, 35, 53
    ]

lista_menores(lista)

Resultado: