29. Data search¶

In this section we are going to study how to search for data within a list. There are numerous Python functions and methods to achieve this, but in this unit we will study search algorithms without your help in order to learn how these algorithms work internally.

Linear data search¶

The simplest algorithm to search for data in a list consists of going through all the elements in the list, one by one, until we find the one we are looking for.

In this case we are going to program a linear search for the smallest element of a list of data.

A variable will save the position of the smallest element found so far and we will update this position as we find other minor elements:

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

The result is as follows:

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

Exercises¶

Write a program with a function that finds the largest element in a list. Call that function with the previous list of numbers to check that the result is element 3 which is worth 99.

Write a function that returns the position of the last even element in a list. If no even number exists, the return result must be the constant None to indicate that none exists.

Call the function with the list of numbers above to check that the result is position 16, number 46.

Clue:

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( ... )

Result:

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

Write a function that returns the position of the first odd element in a list. If no odd number exists, the return result must be the constant None to indicate that none exist.

Call the function with the list of numbers above to check that the result is position 0, number 75.

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

Write a function that counts the number of times an item is found in a list. Call that function to calculate how many times item 5 appears in a list of notes.

Clue:

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

Modify the above program with a loop that finds how many times all the notes from 0 to 10 appear.

Modifies the search program for the smallest element of a list. Add another function to the program that searches again and again for the smallest element, prints it on the screen and deletes it from the list with the del() function. The end result should be that it prints all the elements in the list ordered from smallest to largest.

Clue:

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)

Result: