Recherche trichotomique⚓︎
On souhaite dans cet exercice adapter la recherche dichotomique.
Cet algorithme recherche une valeur dans un tableau dont les éléments sont triés dans l'ordre croissant. À chaque itération, la recherche dichotomique partage le tableau en deux zones séparées par un cas limite. On compare alors la valeur cherchée à la valeur limite. Trois cas se présentent :
- la valeur cherchée est strictement inférieure à la valeur limite : on continue la recherche dans la partie gauche du tableau,
- la valeur cherchée est strictement supérieure à la valeur limite : on continue la recherche dans la partie droite du tableau,
- ces deux valeurs sont égales : on a trouvé l'élément cherché.
On souhaite adapter cet algorithme en partageant le tableau en trois zones (et donc deux valeurs limites) : une zone au début, une au centre et une à la fin. Dès lors, la valeur cherchée est soit :
-
strictement inférieure à la première valeur limite : on continue la recherche dans la partie gauche,
-
égale à la première valeur limite : on a trouvé l'élément cherché,
-
comprise, au sens strict, entre les deux valeurs limites : on continue la recherche dans la partie centrale,
-
égale à la seconde valeur limite : on a trouvé l'élément cherché,
-
strictement supérieure à la seconde valeur limite : on continue la recherche dans la partie droite.
Étude de cas
On cherche la valeur 23.
La zone de recherche s'étale entre les indices 0 et 7 (inclus).
La zone de gauche s'étale entre les indices 0 et 1 (inclus).
L'élément séparant les zones de gauche et centrale est à l'indice 2.
La zone centrale entre les indices 3 et 4 (inclus).
L'élément séparant les zones centrale et de droite est à l'indice 5.
La zone de droite entre les indices 6 et 7 (inclus).
La valeur cherchée ne peut-être que dans la zone centrale.
On a réduit la zone de recherche aux seules cellules d'indices 3 et 4.
Les zones de gauche, centrale et de droite sont vides.
La valeur cherchée est à l'indice 4.
Écrire la fonction trichotomie qui prend en paramètres un tableau d'entiers trié dans l'ordre croissant et une valeur cible et renvoie l'indice de la cible dans le tableau si elle est présente et None si elle est absente.
On garantit que le tableau ne contient que des valeurs distinctes.
On utilisera une recherche trichotomique qui, à chaque étape, partage le tableau en trois zones.
Exemples
>>> tableau = [17, 19, 20, 21, 23, 25, 29, 30]
>>> trichotomie(tableau, 17)
0
>>> trichotomie(tableau, 23)
4
>>> trichotomie(tableau, -1) is None
True
>>> trichotomie(tableau, 24) is None
True
>>> trichotomie(tableau, 50) is None
True
Attention
Les tableaux étudiés sont grands : une recherche linéaire prendra trop de temps.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)