Algorithmes de recherche
Présent ou pas ?
Nous allons enfin répondre à la question posée en introduction du 3.4.
À savoir si on un élément donné est présent ou pas dans une séquence elle-même donnée !
Recherche séquencielle
Si la séquence n’est pas trié, que faire d’autre que vérifier en parcourant la séquence jusqu’à trouver ce fameux élément pour pouvoir affirmer qu' il est présent ou non dans cette séquence.
Ce méthode de recherche a été fait au 3.3 Exemple 2
def est_present(sequence, element):
n = len(sequence)
for i in range(n):
if sequence[i] == element:
return True
return False
» Preuve ? Terminaison et correction prouvée dans ce même 3.3 Exemple 2!
» Compléxité ? Nous avons vu que cette méthode de recherche est de complexité linéaire qui se note \(\mathscr{O}(n)\) pour rappel.
Peut on faire mieux ? Si la liste est triée, a-t-on besoin de parcourir toute la séquence ?
Recherche dichotomique
Sous cet étrange terme, vous connaissez déjà la méthode.
On dispose devant vous de 11 cartes triées par ordre croissante de leur valeur faciale: \(\texttt{A, 2, 3, 4, 6, 7, 8, 10, V, D, R}\).
On choisit une carte parmi celle-ci.
Vous devez déterminer quelle carte a été choisie en posant le minimum de questions auxquelles on ne répondra que \(\texttt{Trouvé !}\) ou \(\texttt{C’est plus !}\) ou \(\texttt{C’est moins !}\).
Comment allez vous procéder ?
Cette méthode appliquée à une séquence peut s’écrire en Python ainsi:
def recherche_dichotomique(sequence, element):
gauche, droite = 0, len(sequence)-1 #element se trouve entre ces deux indices
while gauche <= droite:
milieu = (gauche + droite) // 2 #division entière
if element == sequence[milieu]:
return True
elif element < sequence[milieu]: #element a un indice inférieure à milieu
droite = milieu - 1
else: #element a un indice supérieure à milieu
gauche = milieu + 1
return False #element n'est finalement pas dans la sequence
Algorithme à comprendre pour être capable de le reproduire !
La complexité de l’algorithme de recherche dichotomique est d’ordre logarithmique, notée \(\mathscr{O}{(\log_2(n))}\).
Cet algorithme est donc bien plus rapide que la recherche séquentielle !
À titre d’exemple, en testant sur des séquences ou en utilisant la touche \(log\) de votre calculatrice, on obtient:
| Pb précédent | ||||||||
|---|---|---|---|---|---|---|---|---|
| Longueur de la séquence | \(1=2^0\) | \(4=2^2\) | \(5\) | \(8 = 2^3\) | \(11\) | \(16=2^4\) | \(32 = 2^5\) | \(128 = 2^7\) |
| Nombre maximal d’étapes avec la recherche séquentielle | 1 | 4 | 5 | 8 | 11 | 16 | 32 | 64 |
| Nombre maximal d’étapes avec la recherche dichotomique | 1 | 3 | 3 | 4 | 4 | 5 | 6 | 8 |