Aller au contenu

Dichotomie⚓︎

Compléter la fonction dichotomie :

  • prenant en paramètre un tableau de nombres triés dans l'ordre croissant nombres et une valeur cible

  • renvoyant True si cible est une valeur de nombres, False dans le cas contraire.

Exemples

🐍 Console Python
>>> dichotomie([1, 2, 3, 4], 2)
True
>>> dichotomie([1, 2, 3, 4], 1)
True
>>> dichotomie([1, 2, 3, 4], 4)
True
>>> dichotomie([1, 2, 3, 4], 5)
False
>>> dichotomie([1, 2, 3, 4], 0)
False
>>> dichotomie([1], 1)
True
>>> dichotomie([1], 0)
False
>>> dichotomie([], 1)
False

Remarque

Vous utiliserez obligatoirement un algorithme de recherche dichotomique.

Compléter ci-dessous

###
# Testsbksl-nlassert dichotomie([1, 2, 3, 4], 2)bksl-nlassert dichotomie([1, 2, 3, 4], 1)bksl-nlassert dichotomie([1, 2, 3, 4], 4)bksl-nlassert not dichotomie([1, 2, 3, 4], 5)bksl-nlassert not dichotomie([1, 2, 3, 4], 0)bksl-nlassert not dichotomie([1, 2, 5, 6], 4)bksl-nlassert dichotomie([1], 1)bksl-nlassert not dichotomie([1], 0)bksl-nlassert not dichotomie([], 1)bksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlnombres = list(range(0, 101, 2))bksl-nlfor cible in range(101):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-100, 0, 2))bksl-nlfor cible in range(-100, 0):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-12, 10, 3))bksl-nlfor cible in range(-12, 10):bksl-nl assert dichotomie(nombres, cible) == (cible % 3 == 0)bksl-nlbksl-nl 5/5
def dichotomie(nombres, cible):bksl-nl debut = ...bksl-nl fin = ...bksl-nl while debut <= fin:bksl-nl milieu = ...bksl-nl if cible == ...:bksl-nl return ...bksl-nl elif cible > ...:bksl-nl ...bksl-nl else:bksl-nl ...bksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert dichotomie([1, 2, 3, 4], 2)bksl-nlassert dichotomie([1, 2, 3, 4], 1)bksl-nlassert dichotomie([1, 2, 3, 4], 4)bksl-nlassert not dichotomie([1, 2, 3, 4], 5)bksl-nlassert not dichotomie([1, 2, 3, 4], 0)bksl-nlassert not dichotomie([1, 2, 5, 6], 4)bksl-nlassert dichotomie([1], 1)bksl-nlassert not dichotomie([1], 0)bksl-nlassert not dichotomie([], 1)bksl-nlbksl-nldef dichotomie(nombres, cible):bksl-nl debut = 0bksl-nl fin = len(nombres) - 1bksl-nl while debut <= fin:bksl-nl milieu = (fin + debut)//2bksl-nl if cible == nombres[milieu]:bksl-nl return Truebksl-nl elif cible > nombres[milieu]:bksl-nl debut = milieu + 1bksl-nl else:bksl-nl fin = milieu - 1bksl-nl return Falsebksl-nlbksl-nl

Recherche par dichotomie

Il s'agit d'un algorithme classique. Le tableau pris en paramètre doit obligatoirement être trié.

À chaque itération, on se demande si la valeur centrale est égale à la cible :

  • si oui, on renvoie immédiatement True
  • si non, cette cible est soit :
    • supérieure à la valeur centrale : il faut chercher dans la partie droite du tableau (debut = milieu + 1)
    • inférieure à la valeur centrale : il faut chercher dans la partie gauche du tableau (fin = milieu - 1)

La zone de recherche (l'écart entre fin et debut) se réduit à chaque itération : si on finit par avoir fin < debut, c'est que la cible n'est pas dans le tableau. On sort de la boucle et renvoie False.

Nombre maximal de tours de boucles

Prenons un écart d'indice initial fin - debut égal à \(10^9\), (ce qui est très grand).

Dans le pire des cas, où la cible n'est pas présente, on réalise tous les tours de boucles possibles.

  • Au premier tour, on a un écart environ de \(\frac{10^9}{2}\), c'est à dire de \(5 \times 10^8\)
  • Au deuxième tour, on a un écart environ de \(\frac{5 \times 10^8}{2}\) c'est à dire \(25 \times 10^7\)
  • Ainsi de suite ...
  • Au trentième tour, on a un écart d'environ \(\frac{10^9}{2^{30}}\) c'est à dire d'environ 1.

Ainsi, dans une liste de taille \(10^9\), en au plus environ 30 tours on sait si l'élément cible est présent.