Cours - La recherche dichotomique

La méthode de recherche dichotomique est une approche puissante et efficace utilisée en informatique et dans d'autres domaines pour trouver rapidement des éléments dans des ensembles de données ordonnées.

Aussi connue sous le nom de recherche binaire, cette méthode repose sur un principe simple mais efficace, consistant à diviser à chaque étape l'intervalle de recherche par deux, réduisant ainsi considérablement le nombre d'itérations nécessaires pour trouver la valeur cible.

Dans ce cours, nous explorerons en détail les principes fondamentaux de la recherche dichotomique, ses avantages et ses limitations, ainsi que des exemples concrets pour illustrer son fonctionnement.

Vous avez probablement déjà joué au jeu consistant à "trouver un nombre entre 1 et 100", et proposé la réponse 50.
Si la réponse est "perdu, c'est plus", vous proposez alors 75 et si l'on vous répond "perdu c'est moins" vous proposez finalement 62... C'est un exemple de recherche dichotomique !

Faire une recherche dichotomique, c'est chercher une valeur dans un tableau en prenant le milieu de l'ensemble des solutions possibles (qui sont donc rangées) pour éliminer la moitié des possibilités à chaque étape.

L'algorithme

L'algorithme en pseudo-code peut s'écrire de la manière suivante :

Algorithme de recherche dichotomique

ALGORITHME : recherche_dicho
ENTRÉE :
  tableau : un tableau d'éléments
  element : un élément à chercher dans le tableau
SORTIE : VRAI si l'élément est trouvé, FAUX sinon

DÉBUT
  debut ← 0
  fin ← longueur(tableau) - 1
  trouve ← FAUX
  TANT QUE PAS trouve ET QUE debut ⩽ fin :
    milieu ← partie_entière((debut + fin) / 2)
    SI tableau[milieu] EST ÉGAL À élément :
      trouve ← VRAI
    SINON :
      SI element EST SUPÉRIEUR À tableau[milieu] :
        debut ← milieu + 1
      SINON :
        fin ← milieu - 1
      FIN SI
    FIN SI
  FIN TANT QUE
  RENVOYER trouve
FIN ALGORITHME

Simulation de la recherche dichotomique

Voici un simulateur vous permettant de tester l'algorithme de recherche dichotomique.
(Source : Infoforall)

Simulateur de recherche dichotomique

Valeur cherchée :

	g				c				d
Index	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19
Elément	06	08	09	13	18	37	37	59	60	60	61	68	70	80	80	83	83	89	91	96
					ok

Implémentation en Python

Recherche séquentielle

On a tout d'abord implémenté l'algorithme de recherche séquentielle que nous avons déjà vu auparavant. Cela nous permettra de comparer cet ancien algorithme avec le nouvel algorithme de recherche dichotomique.

def recherche_sequentielle(tableau, element):
    ''' Renvoie True si element est trouvé, False sinon.
    :param tableau: (list[int]) une liste d'éléments
    :param element: (int) l'élément à rechercher
    :return (bool): True ou False '''

    for el in tableau:
        if element == el:
            return True
    return False

Voici une autre version de cette fonction utilisant un parcours par indice plutôt que par élément :

def recherche_sequentielle_v2(tableau, element):
    for i in range(len(tableau)):
        if element == tableau[i]:
            return True
    return False

Recherche dichotomique

La recherche dichotomique peut s'implémenter en Python de la manière suivante :

def recherche_dicho(tableau, element):
    ''' Effectue une recherche dichotomique dans un tableau.
    Renvoie True si element est trouvé, False sinon. '''

    debut = 0
    fin = len(tableau) - 1
    trouve = False
    while not trouve and debut <= fin:
        milieu = (debut + fin) // 2
        if tableau[milieu] == element:
            trouve = True
        else:
            if element > tableau[milieu]:
                debut = milieu + 1
            else:
                fin = milieu - 1
    return trouve

On rappelle que l'opérateur // permet d'obtenir le quotient d'une division euclidienne entre deux nombres.
Ainsi, l'instruction milieu = (debut + fin) // 2 de la ligne 9 permet d'obtenir un nombre entier.

Coût de la recherche dichotomique

Un programme pour analyser les algorithmes de recherche

Voici un programme Python permettant :

• de générer les courbes de l'évolution du nombre de comparaisons effectuées pour les deux algorithmes de recherche, dans le pire des cas.
• de générer les courbes de l'évolution du temps d'exécution mesuré pour les deux algorithmes de recherche, dans le pire des cas.
• d'afficher dans la console un tableau montrant le nombre de comparaisons effectuées pour les deux algorithmes de recherche.

Télécharger le programme analyse_recherche.py

Analyse du nombre de comparaisons

Voici un tableau montrant l'évolution du nombre de comparaisons pour les deux algorithmes de recherche, pour des tailles de tableaux allant de \(N = 2^0\) jusqu'à \(N = 2^{10}\) :

Taille N	Recherche séquentielle	Recherche dichotomique
\(2^0 = 1\)	1	1
\(2^1 = 2\)	2	2
\(2^2 = 4\)	4	3
\(2^3 = 8\)	8	4
\(2^4 = 16\)	16	5
\(2^5 = 32\)	32	6
\(2^6 = 64\)	64	7
\(2^7 = 128\)	128	8
\(2^8 = 256\)	256	9
\(2^9 = 512\)	512	10
\(2^{10} = 1024\)	1024	11

---

Voici des courbes d'évolution du nombre de comparaisons pour les deux algorithmes de recherche. On s'est ici arrêté à une taille \(N = 2^6\) afin de mieux observer la forme des courbes :

Exercice 1

En vous aidant des informations précédentes, déterminez le nombre de comparaisons effectuées pour une taille \(N = 2^{11} = 2048\) :

• dans le cas d'une recherche séquentielle dans le pire des cas (élément recherché absent du tableau),
• dans le cas d'une recherche dichotomique dans le pire des cas (élément recherché absent du tableau).

Exercice 2

Exprimez la taille \(N\) d'un tableau en fonction :

• du nombre de comparaisons, que l'on notera $C_{seq}, nécessaire dans le pire cas pour rechercher un élément dans un tableau de taille \(N\) avec la recherche séquentielle,
• du nombre de comparaisons, que l'on notera $C_{dicho}, nécessaire dans le pire cas pour rechercher un élément dans un tableau de taille \(N\) avec la recherche dichotomique..