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.

Attention. Les algorithmes trouvés sur internet, ne sont pas formellement corrects, et ne marchent pas dans tous les langages, même sur des sites réputés.

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

# Algorithme DICHOTOMIE(val, T)
  gauche ← 0
  droite ← n
  TANT QUE gauche < droite
       milieu ← gauche + (droite - gauche)//2
       SI val < T[milieu]
            droite ← milieu
       SINON SI T[milieu] < val
            gauche ← milieu + 1
       SINON
            RETOURNER milieu
   RETOURNER None

INVARIANT

À tout instant, on a \(0 ≤ gauche ≤ droite ≤ n\).

Zone candidate Si elle est présente, \(val\) ne peut se trouver qu'à l'indice dans l’intervalle \([gauche, droite[\). Autrement dit :

tous les indices strictement avant gauche \([0, gauche[\) ne contiennent pas \(val\)
tous les indices à partir de droite \([droite, n[\) ne contiennent pas \(val\).

Cette formulation embarque le cas où val n'est pas dans le tableau

Cas trouvé Si on a déjà trouvé une position r, alors 0 ≤ r < n et q[r] = key.

INITIALISATION

A l'origine, \(gauche=0\) et \(droite=n\). La valeur recherchée n'est pas en dehors de cet intervalle semi-ouvert.

CONSERVATION**

Faisons l'hypothèse de l'invariant à l'entrée d'une itération et vérifions qu'il 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[ + T[milieu..droite[\]

Nous avons alors exactement 3 possibilités:

Si \(T[milieu]\) est plus grand que la valeur recherchée, vu que \(T\) est trié, c'est que la valeur recherchée n'est pas hors de \(T[gauche..milieu[\) et justement, on valorise \(droite\) à \(milieu\) pour la prochaine itération.
Sinon si \(T[milieu]\) est plus grand, c'est que la valeur recherchée n'est pas hors de \(T[milieu+1 .. droite[\) et justement, on valorise \(gauche\) à \(milieu+1\) pour la prochaine itération
Sinon \(T[milieu]\) porte la valeur recherchée, on retourne l'indice milieu et l'algorithme se termine. (invariant "cas trouvé" conservé)

Dans les cas où l'algorithme se poursuit, l'invariant est donc conservé.

TERMINAISON

Le variant de boucle est la quantité droite-gauche.

Soit on trouve et on termine, soit on divise la taille de l'intervalle par 2 à chaque fois. La quantité droite-gauche est positive et décroit donc strictement. Au pire des cas (la valeur n'est pas dans l'intervalle), la garde \(gauche < droite\) devient donc fausse et l'algorithme termine.

CONCLUSION

On a deux cas possibles:

On a trouvé en cours de route, c'est que l'invariant "cas trouvé" tient, et donc que l'algorithme renvoie correctement la solution.
On n'a pas trouvé en cours de route. C'est que la taille de la zone candidate est nulle par invalidité de la garde, donc que la zone candidate est vide. L'invariant garantit que la valeur ne peux pas être en dehors de la zone de candidate C'est donc que la valeur recherchée n'existe pas.

Dans touts les cas, l'algorithme est totalement correct.

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))\).