Vous êtes sur une version archivée de lyceum.fr de l'année 2021/2022. Revenir au présent.

Chapitre 4: Recherche dichotomique

Plan

Commencons par créer une liste d'éléments
La dichotomie
- Illustration
- Implémentation en Python
Conclusion
Aspects théoriques
- Terminaison: est-ce que l'algorithme s'arrête?
- En plus: Correction: est ce que le résultat est juste?

Programme Officiel

Recherche dichotomique dans un tableau trié

Montrer la terminaison de la recherche dichotomique à l'aide d'un variant de boucle.

Des assertions peuvent être utilisées.

La preuve de la correction peut être présentée par le professeur.

Lien vers le programme complet

Dans ce chapitre, nous allons étudier un algorithme très efficace de recherche d'élément dans un tableau: la recherche dichotomique.

Il illustre une méthode algorithmique très efficace et utile appelée: "Diviser pour régner".

Commencons par créer une liste d'éléments

Pour cela nous allons écrire une fonction pour créer facilement des listes de mots.

Entrée

import random
import string

lettres = string.ascii_lowercase

def create_liste(N, l=3):
    """Renvoie une liste de N mots ayant l lettres"""
    L = []
    # on rend le générateur prédictible en imposant une graine fixe
    random.seed(1789)
    for i in range(N):
        mot = ''.join(random.choice(lettres) for i in range(l))
        L.append(mot)
    # on la trie
    L.sort()
    return L
mots = create_liste(10, 3)
print(mots)

Sortie

['bou', 'bup', 'fuz', 'ryd', 'tfb', 'twn', 'upd', 'xbd', 'xwt', 'yht']

La dichotomie

Nous allons maintenant étudier l'algorithme de recherche par dichotomie. On peut comparer ça à une recherche dans un dictionnaire (qui a eu la bonne idée d'être trié!)

La recherche dichotomique, ou recherche par dichotomie, est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Source Wikipedia

Illustration

Cette image illustre la recherche de l'élément 4 dans tableau trié.

Implémentation en Python

Voici un exemple d'implémentation en Python.

ATTENTION: Il faut bien trier la liste avant d'effectuer la recherche, on va utiliser une méthode implémentée dans Python dans ce chapitre, et nous verrons la semaine prochaine quelques algorithmes de tri.

Entrée

# on crée la liste
mots = create_liste(10, 3)
print("Voici la liste des mots\n", mots)

Sortie

Voici la liste des mots
 ['bou', 'bup', 'fuz', 'ryd', 'tfb', 'twn', 'upd', 'xbd', 'xwt', 'yht']

Définition de la fonction de recherche

Entrée

def recherche_dichotomique(élément, liste):
    # on initialise les indices début 
    # et fin aux extrémités de la liste
    début = 0
    fin = len(liste)
    
    while début <= fin:
        # On se place au milieu de la liste
        milieu = (début + fin) // 2 # il, s'agit d'une division entière
        print("on cherche en: ", milieu, liste[milieu])
        if liste[milieu] == élément:
            print(élément, "trouvé à l'indice:", milieu , liste[milieu])
            return True
        elif liste[milieu] < élément:       
            début = milieu + 1
        else:
            fin = milieu - 1
    print(élément, "non trouvé")
    return False

Appel de la fonction

Entrée

recherche_dichotomique('fuz', mots)

Sortie

on cherche en:  5 twn
on cherche en:  2 fuz
fuz trouvé à l'indice: 2 fuz

Résultat

True

Incroyable on a trouvé en deux fois! Et si on ne trouve pas alors?

Entrée

recherche_dichotomique('aaa', mots)

Sortie

on cherche en:  5 twn
on cherche en:  2 fuz
on cherche en:  0 bou
aaa non trouvé

Résultat

False

Incroyable on a trouvé en trois fois seulement. Il s'agit d'un logarithme ayant une compléxité en $log_2 (n)$ , c'est à dire que pour une liste de n éléments il trouve le résultat en $log_2 (n)$ opérations.

Par exemple:

si n= $10$ : $log_2 (10) = 3,3$
si n= $10^7$ : $log_2 (10~000~000) = 23$

Au lieu de 10 millions d'opérations, on en effectue 23!

Mesurons le temps de recherche de cet algorithme sur une liste de 10 millions d'éléments pour le comparer à la recherche en table.

Attention: on rappelle que la liste doit être triée pour que l'algorithme fonctionne!

Entrée

mots = create_liste(int(1E7), 5)
mots.sort()

Entrée

%%timeit -n1
recherche_dichotomique('abcde', mots)

Sortie

on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  14647 ababy
on cherche en:  17088 abegy
on cherche en:  15867 abcer
on cherche en:  15257 abbdl
on cherche en:  15562 abbro
on cherche en:  15714 abbxt
on cherche en:  15790 abcay
on cherche en:  15828 abccm
on cherche en:  15847 abcdk
on cherche en:  15837 abccz
on cherche en:  15842 abcdd
on cherche en:  15844 abcdd
on cherche en:  15845 abcde
abcde trouvé à l'indice: 15845 abcde
The slowest run took 19.29 times longer than the fastest. This could mean that an intermediate result is being cached.
1.6 ms ± 2.34 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Il nous a fallu à peine 2 ms cette fois-ci, au lieu de 600ms pour la recherche en table, c'est 300 fois moins, et plus la liste sera grande, et plus l'écart sera important.

Voyons si l'élément est non trouvé.

Entrée

%%timeit -n1
recherche_dichotomique('aaaaaa', mots)

Sortie

on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
on cherche en:  5000000 naalx
on cherche en:  2499999 gncqd
on cherche en:  1249999 dgnwz
on cherche en:  624999 bqiqg
on cherche en:  312499 aveee
on cherche en:  156249 akpdh
on cherche en:  78124 afhut
on cherche en:  39061 acqxs
on cherche en:  19530 abipe
on cherche en:  9764 aarlr
on cherche en:  4881 aaisw
on cherche en:  2440 aaeki
on cherche en:  1219 aacel
on cherche en:  609 aabcs
on cherche en:  304 aaaov
on cherche en:  151 aaahg
on cherche en:  75 aaadg
on cherche en:  37 aaabv
on cherche en:  18 aaaav
on cherche en:  8 aaaah
on cherche en:  3 aaaad
on cherche en:  1 aaaab
on cherche en:  0 aaaab
aaaaaa non trouvé
The slowest run took 19.65 times longer than the fastest. This could mean that an intermediate result is being cached.
2.97 ms ± 2.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

On effectue seulement 23 itérations en à peine 3 ms. Voila pourquoi la dichotomie est une méthode si puissante, la recherche a été 300 fois plus rapide qu'avec la recherche en table sur cette liste de 10 millions de mots.

Remarque: l'algorithme écrit nécessiterait quelques retouches pour afficher le non-trouvé lorsque l'élément chérché est au dessus du dernier élément!

Conclusion

Nous avons vu sur cet exemple en quoi la recherche dichotomique était une méthode efficace pour rechercher un élément dans un tableau trié.

Cela nous a permis d'introduire la notion de complexité d'un algorithme qui vise à évaluer l'efficacité des algorithmes en mesurant le nombre d'opérations nécessaires à la finalisation d'un algorithme.

Cette méthode n'est qu'un exemple de nombreux autres algorithmes utilisant une méthode générale appelée "Diviser pour régner".

En informatique, diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) est une technique algorithmique consistant à :

Diviser : découper un problème initial en sous-problèmes ;

Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;

Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

Image par Fschwarzentruber --- [Travail personnel]{.int-own-work lang="fr"}, CC BY-SA 4.0, Lien

Cette technique fournit des algorithmes efficaces pour de nombreux problèmes, comme la recherche d'un élément dans un tableau trié (recherche dichotomique), le tri (tri fusion, tri rapide), la multiplication de grands nombres (algorithme de Karatsuba) ou la transformation de Fourier discrète (transformation de Fourier rapide). Source Wikipedia

Aspects théoriques

Nous allons démontrer la terminaison et la correction de l'algorithme de façon théorique.

Nous avons vu qu'il était possible d'utiliser des jeu de tests pour vérifier qu'un programme fonctionne, cependant il n'est jamais possible de créer des tests pour toutes les situations connues.

C'est pour cela qu'on utilise parfois des outils plus abstarits pour démontrer que nos algorithmes "fonctionnent" dans tous les cas.

Terminaison: est-ce que l'algorithme s'arrête?

On voit qu'à chaque tour de boucle, le nombre d'élements à tester entre $i$ et $j$ est divisé par 2.

Après un nombre d'itérations fini, ce nombre d'éléments est inférieur ou égal à 1 et la boucle s'arrête. (Si N est le nombre d'éléments ce nombre d'itérations est $log_2(N)$

Entrée

# On prend 128 éléments = 2**8
i = 0
j = 127
compteur = 0
while i < j:
    j = (i + j) //2
    compteur += 1
print(compteur) # 8 tours

Sortie

Entrée

# On prend 2048 éléments = 2**11
i = 1
j = 2048
compteur = 0
while i < j:
    j = (i + j) //2
    compteur += 1
print(compteur) # 11 tours

Sortie

En plus: Correction: est ce que le résultat est juste?

L'algorithme renvoit-il la bonne valeur?

La démonstration est délicate est non exigible.

[Informatique et sciences du numérique Spécialité ISN en terminale S - Avec des exercices corrigés et des idées de projets par Gilles Dowek]{.cite-source}

Ensuite, pour démontrer que la réponse donnée par l'algorithme est correcte, on commence par montrer que si la chaîne de caractères $s$ est dans la table, alors son indice appartient toujours à l'intervalle $[i, j]$ . Cette propriété est un invariant de la boucle, c'est-à-dire une propriété qui reste vraie à chaque exécution du corps de la boucle.

Ici, quand on réduit l'intervalle $[i, j]$ à l'intervalle $[i, k - 1]$ par exemple, c'est parce que l'on sait que la chaîne $s$ est avant la chaîne $nom[k]$ dans l'ordre alphabétique et donc que l'indice de la chaîne $s$ , s'il existe, n'est pas dans l'intervalle $[k, j]$ . La propriété reste donc vraie jusqu'à la fin de l'exécution de la boucle. Enfin, on montre que quand on sort de la boucle, l'intervalle $[i, j]$ est soit le singleton $[i, i]$ , soit l'intervalle vide $[i , i-1]$ . Dans les deux cas, $i$ est compris entre les valeurs minimale et maximale de départ.

Pour cela, on montre un autre invariant de la boucle : si l'intervalle $[i, j]$ n'est pas vide, alors ses bornes $i$ et $j$ sont comprises entre les valeurs minimale et maximale de départ, et s'il est vide, alors sa borne inférieure $i$ est comprise entre les valeurs minimale et maximale de départ.

Si l'intervalle $[i, j]$ contient au moins trois points, c'est-à-dire si $i + 2 \le j$ , il n'est pas difficile de montrer que les nombres $k - 1$ et $k + 1$ , où $k = (i + j) // 2$ , sont tous les deux compris entre $i$ et $j$ au sens large. Le nouvel intervalle $[k, k]$ , $[i, k - 1]$ ou $[k + 1, j]$ est contenu dans $[i, j]$ et donc ses bornes sont comprises entre les valeurs minimale et maximale de départ.

Si l'intervalle $[i, j]$ contient deux points, c'est-à-dire si $j = i + 1$ , alors $k = (i + j) // 2$ est égal à $i$ . Le nombre $k + 1$ est égal à $j$ : il est compris entre $i$ et $j$ au sens large. En revanche, le nombre $k - 1$ est égal à $i - 1$ . Dans ce cas, le nouvel intervalle est $[i, i]$ ou $[ j, j]$ dont les bornes sont comprises entre les valeurs minimale et maximale de départ, ou l'intervalle vide $[i, i - 1]$ dont la borne inférieure $i$ est comprise entre les valeurs minimale et maximale de départ.

On sort de la boucle quand l'intervalle $[i, j]$ contient zéro ou un point. Dans un cas comme dans l'autre, l'indice $i$ est compris entre les valeurs minimale et maximale de départ. Si la chaîne de caractères nom[i] est identique à $s$ , on a trouvé l'indice de la chaîne $s$ dans la liste $nom$ ; si ce n'est pas le cas, la chaîne $s$ n'est pas dans la table.