MetMat
← Retour aux méthodes

Comment implémenter une recherche dichotomique dans une liste triée ?

En maintenant deux indices gauche et droite, en comparant l'élément médian, et en divisant l'intervalle par deux à chaque itération

L'objectif

Rechercher efficacement un élément dans une liste triée en réduisant de moitié l'intervalle de recherche à chaque itération.

Le principe

Si L est triée par ordre croissant et m = (g+d)//2, alors comparer L[m] à la cible v permet d'éliminer la moitié de l'intervalle : si v < L[m] on poursuit dans [g, m-1], sinon dans [m+1, d] ; le coût est en O(log⁡2n)O(\log_2 n).

La méthode
  1. 1
    Je pose gauche = 0 et droite = len(L) - 1, les bornes de l'intervalle de recherche.
  2. 2
    Tant que gauche <= droite, je calcule m = (gauche + droite) // 2 et je compare L[m] à v.
  3. 3
    Si L[m] == v, je renvoie l'indice m ; si L[m] < v, je pose gauche = m + 1 ; sinon droite = m - 1.
  4. 4
    À la sortie de la boucle (intervalle vide), je renvoie -1 ou False pour signaler l'absence.

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.