I. Maximum, minimum

C'est très courant de chercher le maximum ou le minimum d'une liste.

def minimum(L):
    """renvoie le minimum de la liste L et son indice"""
    val_min = L[0]
    i_min = 0
    #on commence à 1 car on a déjà vu l'élément 0
    for i in range(1, len(L)):
        if L[i] < val_min:
            val_min = L[i]
            i_min = i

    return (val_min, i_min)

minimum([5, 3, 8, 1, 9, 2])

II. Recherche d'un élément dans une liste

a) Recherche "naïve"

def recherche(L, x):
    """renvoie True si x est dans L, False sinon."""
    for y in L:
        if x == y:
            return True
    return False

print(recherche([3, 1, 4, 1, 5], 4))
print(recherche([3, 1, 4, 1, 5], 7))

b) Recherche dans une liste triée : la dichotomie

Le mot dichotomie veut dire "couper en deux". C'est une méthode très courante pour faire des algorithmes plus efficaces : on coupe le problème en deux, et soit on traite les parties indépendamment (tri fusion, tri rapide...), soit on arrive à ne traiter qu'une seule des deux parties (recherches, exponentiation rapide...).

On a vu comment on peut trier une liste. Comment utiliser ce tri pour chercher un élément plus vite ?

Idée : on regarde au milieu de la liste.

• Si l'élément du milieu est plus petit que x, alors x est dans la deuxième moitié.
• Sinon, dans la première moitié.

Par exemple, voici les étapes de la recherche de 2 dans la liste [-1, 0, 1, 2, 3, 4, 5, 10, 123, 124]. À chaque étape, la partie de la liste où l'on cherche encore est en gras :

def recherche_dicho(L, x):
    """Si L est une liste triée dans l'ordre croissant, renvoie l'indice de x dans L, ou bien None si x n'est pas dans L."""
    i = 0 #borne inf incluse
    j = len(L) #borne sup exclue

    while (j - i) > 0:
        milieu = (i + j) // 2
        if L[milieu] < x:
            i = milieu + 1
        elif L[milieu] > x:
            j = milieu
        else: #cas où L[milieu] == x
            return milieu
    return None

L = [-1, 0, 1, 2, 3, 4, 5, 10, 123, 124]
print(recherche_dicho(L, 2))
print(recherche_dicho(L, 6))

Pour visualiser la recherche, voici la même fonction, qui note en plus chaque étape (la partie de la liste où l'on cherche encore, en vert, et le milieu, en rouge), pour l'animer avec animer_liste :

On peut aussi suivre les valeurs des variables à chaque tour de boucle avec tracer_variables :

III. Recherche du zéro d'une fonction

Supposons qu'on ait une fonction croissante et qu'on cherche où elle s'annule sur un intervalle , avec et .

On peut appliquer le même principe ! On regarde le signe de au milieu de l'intervalle, et on garde la moitié dans laquelle change de signe.

def recherche_zero(f, a, b, eps):
    """Si f(a) < 0 et f(b) > 0, renvoie un zéro de f sur [a, b] à eps près."""
    while b - a > eps:
        milieu = (a + b) / 2
        if f(milieu) < 0:
            a = milieu
        else:
            b = milieu
    return (a + b) / 2

Par exemple, pour trouver une valeur approchée de , on cherche le zéro de sur :

def f(x):
    return x ** 2 - 2

recherche_zero(f, 0, 2, 1e-6)

Pour visualiser les étapes, voici la même fonction, qui renvoie en plus la liste des intervalles successifs, que l'on anime avec animer_dichotomie :

On veut trouver le nombre de tours de boucle avant que le programme s'arrête. À chaque tour, la taille de l'intervalle est divisée par deux : après tours, elle vaut . Le programme s'arrête donc quand :

On a donc, en ordre de grandeur de complexité, tours de boucle (et d'opérations, car chaque tour de boucle fait un nombre constant d'opérations).

Exercices

def indice_min(L):
    i_min = 0
    for i in range(1, len(L)):
        if L[i] < L[i_min]:
            i_min = i
    return i_min

def premiere_occurrence(L, x):
    i, j = 0, len(L)
    trouve = None
    while j - i > 0:
        milieu = (i + j) // 2
        if L[milieu] < x:
            i = milieu + 1
        else:
            if L[milieu] == x:
                trouve = milieu
            j = milieu
    return trouve

recherche_zero(lambda x: x ** 3 - 10, 0, 10, 1e-6)   # environ 2.154435