Skip to content

Recherche dichotomique

Il s'agit ici de proposer un algorithme efficace pour le problème SEARCH sur un tableau trié.

Introduction

Plus ou moins

Règles: La machine doit deviner un nombre entre 0 et \(n\) que vous aurez choisi.

Question: A votre avis, de quelle manière doit jouer l'ordinateur pour gagner le plus vite possible?

Ecrire un programme qui: - Demande au joueur: 

Je vais essayer de deviner un entier compris entre 1 et n
Donne moi la valeur de n et choisis un entier dans ta tête

  • L'utilisateur entre par exemple 100.

  • L'ordinateur boucle alors en affichant une proposition et en demandant (35 est un exemple de proposition de l'ordinateur):

    35. Ton nombre est-il plus grand, moins grand, ou égal? [+/-/=]

  • Ce à quoi l'utilisateur répond par un des caractères '+', '-' ou '='

  • Le programme se termine lorsque l'ordinateur a trouvé (l'utilisateur a répondu que c'était le bon nombre)

Recherche dichotomique sur tableau trié

La recherche dichotomique s'inspire de la manière la plus efficace de jouer au "plus ou moins" en divisant l'intervalle de recherche par deux à chaque tentative.

En voici une Visualisation

Puis, en voici l'algorithme:

En première lecture, ignorez les lignes 1 et 2. 

**ENTRÉE** 
- Un tableau d'entiers T[0..n-1]
- Un entier à trouver val
**SORTIE** 
- L'indice du premier élément trouvé s'il existe
- None si la valeur n'appartient pas au tableau.

# Algorithme DICHOTOMIE(T, val)
1. SI n==0 OU T[0]>val
2.      RETOURNER None
3. gauche ← 0
4. droite ← n-1
5. TANT QUE gauche <= droite
6.      milieu ← gauche + (droite - gauche)//2
7.      SI T[milieu] = valeur
8.          RETOURNER milieu
9.      SINON SI T[milieu] > valeur
10.         droite ← milieu - 1
11.     SINON
12.         gauche ← milieu + 1
13. RETOURNER None

Le variant de boucle est la quantité droite-gauche+1. Quand elle est égale à 0, l'algorithme termine.

L'invariant est la propriété "La valeur recherchée est dans \(T[gauche..droite]\)"

INITIALISATION A l'origine, \(gauche=0\) et \(droite=n-1\). La valeur recherchée est bien dans \(T[gauche..droite]\)

CONSERVATION

Faisons l'hypothèse que "La valeur recherchée est dans \(T[gauche..droite]\)" à l'entrée d'une itération et vérifions que c'est toujours vrai à l'itération suivante.

Nous commençons par calculer l'indice milieu de l'intervalle \([gauche; droite]\).

Nous pouvons donc décomposer notre tableau ainsi:

\[T[gauche..milieu-1] + T[milieu..milieu] + T[milieu+1..droite]\]

Nous avons alors exactement 3 possibilités:

  • Si \(T[milieu]\) porte la valeur recherchée, on retourne l'indice milieu et l'algorithme se termine correctement.
  • Sinon si \(T[milieu]\) est plus grand que la valeur recherchée, vu que \(T\) est trié, c'et que la valeur recherchée est dans \(T[gauche..milieu-1]\) et justement, on valorise \(droite\) à \(milieu-1\) pour la prochaine itération.
  • Sinon, c'est que la valeur recherchée est dans \(T[milieu+1 .. droite]\) et justement, on valorise \(gauche\) à \(milieu+1\) pour la prochaine itération

Dans le premier cas, l'algorithme se termine correctement. Dans les cas où il se poursuit, l'invariant est conservé.

TERMINAISON

  1. Dans le cas où la valeur est bien présente dans le tableau: Dans le pire des cas, la taille de l'intervalle \([gauche;droite]\) va être divisée par deux de manière continue jusqu'à atteindre 1 et la conservation de l'invariant garantit que la valeur se trouvera dans \(T[gauche;droite]\), avec \(gauche=droite=milieu\). L'algorithme s'arrête donc bien en renvoyant \(T[milieu]\) (Note: la taille d'un intervalle d'entiers est le nombre d'entiers qu'il contient)

  2. Dans le cas où la valeur n'est pas dans le tableau: La taille de l'intervalle \([gauche;droite]\) va être divisée par deux de manière continue jusqu'à atteindre 1. Cependant, contrairement au cas précédent, l'indice \(milieu\) ne portera pas la valeur recherchée. Ainsi, que la valeur recherchée soit plus grande ou plus petite que \(T[milieu]\), on aura gauche>droite et la boucle se terminera. L'algorithme renverra None.

  3. Dans le cas où la valeur est plus petite que le premier élément du tableau: Ce cas est traître en implémentation, mais nous engage à bien définir le domaine de valeurs de nos variables. On se trouvera à la fin avec \(milieu=0\), et \(T[milieu]>valeur\). On va donc exécuter \(droite ← milieu - 1\), ce qui va positionner \(milieu\) à \(-1\) C'est un problème car le domaine de valeurs d'un indice de tableau est un entier non signé (positif). Notez bien que les bidouilles d'indices négatifs sont propres à python. Par exemple, Rust lèvera une erreur sur ce cas car il n'autorisera pas la variable droite à prendre la valeur -1 attendu qu'elle est obligatoirement positive pour servir d'indice de tableau. C'est pour ça qu'existent les lignes 1 et 2. On commence par vérifier que la valeur recherchée n'est pas inférieure au premier élément pour ne jamais tomber sur ce cas. On en profite aussi pour régler son compte au cas du tableau vide, car de la même manière, droite ne peut pas valoir -1 en 4ème ligne.

Implémentation python

Ecrire et tester une fonction recherche_dicho(v: int, t: list[int]) -> int|None implémentant l'algorithme décrit.

Complexité

On s'intéresse à la phrase:

"Dans le pire des cas, la taille de l'intervalle \([gauche;droite]\) va être divisée par deux de manière continue jusqu'à atteindre 1."

Ce qui nous intéresse pour la complexité, c'est ce nombre de divisions entières par 2, car toutes les opérations au sein de la boucle sont en temps constant (Elles comptent donc pour 1)

Il existe une fonction mathématique qui nous donne le nombre de fois qu'il faut diviser un nombre entier \(n\) par 2 pour obtenir 1. Il s'agit de la fonction logarithme entier de base 2. Il faut diviser \(n\) \(\lfloor \log_2(n) \rfloor\) fois par 2 pour obtenir 1.

On dit que l'algorithme est en \(\mathcal{O}(log(n))\).

Ces algorithmes sont aussi considérés comme faisant partie de la classe \(P\) car \(\log(n)\) est dominée par les fonctions polynômiales.

Pour aller plus loin

Etudiez l'algorithme alternatif proposé ci-dessous. Notez qu'il ne possède pas de boucle:

**ENTRÉE** 
- Un tableau d'entiers T[0..n-1]
- Un entier à trouver val
- un indice de début de recherche gauche
- un indice de fin de recherche droite
**SORTIE** 
L'indice du premier élément trouvé, None si la valeur n'appartient pas au tableau.

# Algorithme DICHOTOMIE(T, val, gauche, droite)
1. SI n==0 OU T[gauche]>val OU gauche > droite
2.      RETOURNER None
3. milieu ← gauche + (droite - gauche)//2
4. SI T[milieu] = valeur
5.      RETOURNER milieu
6. SINON SI T[milieu] > valeur
7.     RETOURNER DICHOTOMIE(T, val, gauche, milieu-1)
8. SINON
9.     RETOURNER DICHOTOMIE(T, val, milieu + 1, droite)