29. Cerca de dades¶

En aquesta secció estudiarem com buscar dades dins d’una llista. Hi ha nombroses funcions i mètodes Python per aconseguir -ho, però en aquesta unitat s’estudiaran els algoritmes de cerca sense la seva ajuda per aprendre com funcionen aquests algoritmes internament.

Cerca de dades lineals¶

L’algoritme més senzill per buscar dades d’una llista consisteix a recórrer tots els elements de la llista, un per un, fins que trobem la que busquem.

En aquest cas, programem una cerca lineal de l’element inferior d’una llista de dades.

Una variable mantindrà la posició de l’element inferior que es troba fins ara i actualitzarem aquesta posició a mesura que trobem altres elements menors

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 resultat és el següent

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

Exercicis¶

Escriviu un programa amb una funció que busqui l’element principal d’una llista. Truqueu a aquesta funció amb la llista de números anterior per verificar que el resultat és l’element 3 per valor de 99.

Escriviu una funció que retorna la posició de l’últim element de parell d’una llista. Si no hi ha cap número de parell, el resultat retornat ha de ser la constant `` cap '' per indicar que no n'hi ha cap.

Truqueu a la funció amb la llista de números anterior per verificar que el resultat és la posició 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( ... )

Resultat

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

Escriviu una funció que retorna la posició del primer element estrany d’una llista. Si no hi ha cap número estrany, el resultat retornat ha de ser la constant `` cap '' per indicar que no n'hi ha cap.

Truqueu a la funció amb la llista de números anterior per verificar que el resultat és la posició 0, número 75.

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

Escriviu una funció que tingui els temps que es troba un element en una llista. Truqueu a aquesta funció per calcular quantes vegades apareix l’element 5 en una llista de notes.

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')

Modifiqueu el programa anterior amb un bucle que busca quantes vegades totes les notes apareixen de 0 a 10.

Modifiqueu el programa de cerca de l’element menor d’una llista. Afegiu al programa una altra funció que va i de nou l’element menor, que l’imprimeix a la pantalla i que el suprimeix de la llista amb la funció `` `` `. El resultat final ha de ser imprimir tots els elements de la llista ordenats de menys a més gran.

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)

Resultat