La méthode de recherche par dichotomie consiste à chercher une valeur dans une liste en réduisant progressivement la taille de la liste. Dichotomie signifie couper. On coupe la liste de recherche en deux ce qui la réduit très rapidement.

On considère la fonction définie par $f(x) = -\frac{x^3}{4} + \frac{9\,x^2}{2} - 13\,x - 59$ dont on donne ci-dessous la représentation graphique sur l'intervalle $[0;10]$.

Voici comment se passe la recherche :

• La zone de recherche initiale est $[0;10]$. On constate que $f(0) = -59$ et $f(10) = 11$. Il y a donc au moins une solution à $f(x) = 0$ avec $x\in[0;10]$.
• On cherche le milieu de $[0;10]$. C'est $5$. On calcule $f(5) = -42,75$. On déduit donc que la solution recherchée doit se trouver dans $[5;10]$.
• On cherche le milieu de $[5;10]$. C'est $7,5$. On calcule $f(7,5) = -8,84375 < 0$. On déduit donc que la solution recherchée doit se trouver dans $[7,5;10]$.

Entrées: a, b, bornes de l'intervalle de recherche
         f la fonction
         e taille de l'intervalle final
Prérequis: a < b ; f(a) et f(b) de signe opposé
Renvoie une approximation de la solution à f(x) = 0
  contenue dans [a;b], et avec une erreur inférieur à e
DÉBUT
    TANT QUE taille [a;b] >= e RÉPÉTER
        m prend la valeur du milieu de [a;b]
        SI f(m) et f(a) de signe opposé ALORS
            b prend la valeur de m
        SINON
            a prend la valeur de m
        FIN
    FIN
    RENVOYER (a + b)/2
FIN

Complétez et testez.

def dichotomie(a:float, b:float, f, e:float) -> float:
    """
    a,b : bornes de l'intervalle
    f: fonction
    e: taille maximale de la solution désirée
    renvoie une approx de la solution à f(x) = 0,
      solution dans [a;b], avec une erreur < e
    """
    assert a < b
    assert f(a) * f(b) <= 0 # Vérifie que f(a) et f(b) de signe opposé
    assert e > 0
    
    # à vous
    
if __name__ == "__main__":
    # zone de test
    def f(x):
        return -1/4*x**3 + 9/2*x**2 - 13*x - 59

    sol = dichotomie(0,10,f,1e-6)
    print(sol)