====== Recherche par dichotomie ======

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.

===== Exemple =====

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]$.

{{ ./dichotomie_fonction.png?nolink&400 |}}

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]$.

{{ ./dichotomie_fonction_2.png?nolink&400 |}}

<WRAP tip>
Les valeurs exactes des calculs successifs n'ont pas d'importance. Ce qui importe c'est de savoir le signe. C'est parce que $f(0)$ et $f(10)$ sont de signes opposés que l'on est certain de trouver une solution entre $0$ et $10$ -- Considérant que la fonction est continue, soit, dit simplement, qu'elle ne peut passer de $f(0)<0$  à $f(10)>0$ sans passer par $0$.
</WRAP>

===== Algorithme =====

<code lang-none linenumbers>
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
</code>

===== Implémentation =====

Complétez et testez.

<code python linenums>
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)
</code>