Algorithme de recherche dichotomique dans un tableau
Plan de tutoriel
1- Principe de l'algorithme de recherche dichotomique
2- Algorithme de recherche dichotomique
3- Programme Python
Principe de l'algorithme de recherche dichotomique
La recherche dichotomique est une méthode efficace permettant de rechercher une valeur dans un tableau trié dans l’ordre croissant. Son principe consiste à comparer la valeur recherchée avec l’élément situé au milieu de la partie du tableau étudiée.
Au début de la recherche, on considère l’ensemble des éléments du tableau comme zone de recherche. Deux indices, a et b, permettent de délimiter cette zone : a représente l'indice du premier élément et b celui du dernier élément. L’indice p de l’élément situé au milieu est ensuite calculé à l’aide de la formule p = (a + b) // 2.
La valeur recherchée x est alors comparée à l’élément t[p] situé au milieu. Si x est égale à t[p], la recherche est terminée car la valeur a été trouvée.
Si x est supérieure à t[p], comme le tableau est trié dans l’ordre croissant, tous les éléments situés à gauche de p sont inférieurs à x. Cette partie peut donc être éliminée et la recherche continue uniquement dans la partie droite en affectant a = p + 1.
À l’inverse, si x est inférieure à t[p], tous les éléments situés à droite de p sont supérieurs à x. Cette partie peut alors être éliminée et la recherche continue uniquement dans la partie gauche en affectant b = p - 1.
Ces étapes sont répétées jusqu’à ce que la valeur soit trouvée ou que la zone de recherche devienne vide. Dans ce dernier cas, cela signifie que la valeur recherchée n’existe pas dans le tableau. L’algorithme retourne alors True si la valeur a été trouvée et False dans le cas contraire.
L’avantage principal de la recherche dichotomique est qu’elle réduit de moitié la zone de recherche à chaque étape. Elle est donc beaucoup plus rapide qu’une recherche séquentielle lorsque le tableau contient un grand nombre d’éléments.
Algorithme de recherche dichotomique
Dans cet algorithme, On va utiliser trois fonctions et une procédure :
- la fonction saisie_taille
- la procédure remplir
- la fonction saisie
- la fonction recherche
Algorithme du programme Principal
Cet algorithme principal permet de rechercher une valeur donnée dans un tableau d’entiers trié dans l’ordre croissant, en utilisant une recherche dichotomique.
Son fonctionnement est organisé en plusieurs étapes :
1- Saisie de la taille du tableau
Il appelle la fonction saisie_taille() afin de déterminer le nombre n d’éléments du tableau.
2- Remplissage du tableau
Il appelle la procédure remplir(t, n) pour saisir les n éléments. Cette procédure veille à ce que les valeurs soient saisies dans l’ordre croissant, condition nécessaire pour effectuer une recherche dichotomique.
3- Saisie de la valeur recherchée
Il appelle la fonction saisie() afin de récupérer la valeur x que l'utilisateur souhaite rechercher.
4- Recherche de la valeur
Il appelle la fonction recherche(t, n, x), qui effectue la recherche dichotomique dans le tableau. Cette fonction retourne Vrai si x est présente et Faux dans le cas contraire.
5- Affichage du résultat
Enfin, l'algorithme affiche un message indiquant si la valeur recherchée a été trouvée ou non.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
Algorithme Recherche_dichotomique Debut # Appeler la fonction saisie_taille() # afin d'obtenir le nombre d'éléments # qui seront utilisés dans le tableau. n <-- saisie_taille() # Afficher un message indiquant # le début du remplissage du tableau. Ecrire("***Remplissage du tableau***") # Appeler la procédure remplir() # afin de saisir les n éléments du tableau. # # La procédure impose que les éléments soient # saisis dans l'ordre croissant. # # Exemple : # 2, 5, 8, 12, 17, 21, 30 remplir(t, n) # Appeler la fonction saisie() # afin de demander à l'utilisateur # la valeur qu'il souhaite rechercher. x <-- saisie() # ========================================================== # Recherche de la valeur # ========================================================== # Appeler la fonction recherche() # afin de rechercher x dans le tableau. # # La fonction recherche() retourne : # - Vrai si x existe dans le tableau ; # - Faux si x n'existe pas dans le tableau. Si recherche(t, n, x) == Vrai alors # Afficher un message indiquant # que la valeur recherchée a été trouvée. Ecrire(x, " est trouvé") Sinon # Afficher un message indiquant # que la valeur recherchée n'a pas été trouvée. Ecrire(x, " n'a pas été trouvé") Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| x | entier |
| t | tableau des entiers |
La fonction saisie_taille
La fonction saisie_taille() permet de saisir et de contrôler le nombre d’éléments n du tableau. Elle demande à l’utilisateur de donner une valeur comprise entre 2 et 14.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Fonction saisie_taille():entier # La variable test permet de contrôler # si la taille saisie est correcte. test <-- Faux # Répéter la saisie tant que la valeur # n'est pas comprise entre 2 et 14. Tant que test = Faux faire # Demander à l'utilisateur de saisir # la taille du tableau. Ecrire("donner n entre 2 et 14: ") Lire(n) # Vérifier que n est comprise entre 2 et 14. Si 2 <= n <= 14 alors # La taille saisie est correcte. test <-- Vrai Fin si Fin tant que # Retourner la taille du tableau. retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir
La procédure remplir(t, n) permet de remplir les n premières cases du tableau t avec des entiers dans l’ordre croissant.
Le premier élément est saisi directement.
Pour chaque élément suivant, le programme vérifie qu’il est strictement supérieur à l’élément précédent. Si la valeur saisie ne respecte pas l’ordre croissant, une nouvelle saisie est demandée.
Ainsi, à la fin de la procédure, le tableau contient des éléments strictement croissants.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
Procédure remplir(var t:tab; n:entier) # Saisir le premier élément du tableau. Ecrire("donner un element du tableau : ") Lire(t[0]) # Parcourir les cases restantes du tableau. Pour i de 1 à n-1 faire # La variable test permet de vérifier # si l'élément saisi respecte l'ordre croissant. test <-- Faux # Répéter la saisie tant que l'élément # n'est pas supérieur à l'élément précédent. Tant que test = Faux: # Saisir un élément du tableau. Ecrire("donner un element du tableau : ") Lire(t[i]) # Vérifier que l'élément courant est supérieur # à l'élément précédent. Si t[i] > t[i - 1] alors # L'ordre croissant est respecté. test <-- Vrai Finsi Fin tant que Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| test | booléen |
La fonction saisie
La fonction saisie() permet de demander à l'utilisateur de saisir une valeur entière à rechercher dans le tableau, puis de retourner cette valeur.
|
1 2 3 4 5 |
Fonction saisie():entier Ecrire("donner une valeur à rechercher ") Lire(n) retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction recherche
La fonction recherche(t, n, x) a pour rôle de rechercher efficacement la valeur x dans un tableau t de n éléments triés dans l’ordre croissant, en utilisant la méthode de recherche dichotomique.
Elle commence par définir une zone de recherche comprise entre les indices a et b. À chaque étape, elle calcule l'indice p de l'élément situé au milieu de cette zone, puis compare x avec t[p].
Si x = t[p], la valeur recherchée est trouvée et la fonction retourne Vrai.
Si x > t[p], la recherche continue uniquement dans la partie droite du tableau en faisant a ← p + 1.
Si x < t[p], la recherche continue uniquement dans la partie gauche en faisant b ← p - 1. La recherche se poursuit jusqu'à ce que x soit trouvée ou que la zone de recherche devienne vide (a > b).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
Fonction recherche(t:tab; n:entier; x:entier) : # a représente l'indice de début # de la zone dans laquelle on recherche x. # # Au début, la recherche commence # à la première case du tableau. a <-- 0 # b représente l'indice de fin # de la zone dans laquelle on recherche x. # # La dernière case utilisée possède # l'indice n - 1. b <-- n - 1 # resultat indique si la valeur x # a été trouvée dans le tableau. # # Au début de la recherche, x n'est pas encore trouvée. resultat <-- Faux # Répéter la recherche tant que : # # 1. x n'a pas encore été trouvée ; # 2. la zone de recherche n'est pas vide. # # La condition a <= b signifie qu'il reste # au moins une case à examiner. Tant que (resultat = Faux) et (a <= b) faire # Calculer l'indice de l'élément situé # au milieu de la zone de recherche. # # // représente une division entière. p <-- (a + b) div 2 # Comparer la valeur recherchée x # avec l'élément situé au milieu du tableau. Si x = t[p] alors # x est égale à l'élément situé # à la position p. # # La valeur recherchée a donc été trouvée. resultat <-- Vrai Sinon Si x > t[p] alors # x est supérieure à l'élément du milieu. # # Le tableau est trié dans l'ordre croissant. # Tous les éléments situés à gauche de p # sont donc inférieurs à x. # # Il est inutile de continuer la recherche # dans cette partie. # # On déplace alors le début de la zone # de recherche après la position p. a <-- p + 1 Sinon Si x < t[p] alors # x est inférieure à l'élément du milieu. # # Comme le tableau est trié dans l'ordre croissant, # tous les éléments situés à droite de p # sont supérieurs à x. # # Il est donc inutile de rechercher dans # cette partie. # # On déplace la fin de la zone de recherche # avant la position p. b <-- p - 1 Fin si # Retourner le résultat de la recherche. # # Vrai : x a été trouvée. # Faux : x n'a pas été trouvée. Fin tant que retourner resultat Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| p | entier |
| a | entier |
| b | entier |
| resultat | booléen |
Programme en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Importer la fonction array de NumPy. # Elle permet de créer et de manipuler des tableaux. # ========================================================== # Création du tableau # ========================================================== # Créer un tableau de 100 éléments. # Toutes les cases sont initialisées à 0. # # Le tableau peut donc contenir au maximum 100 éléments. # Dans ce programme, seules les n premières cases # seront utilisées. t = array([int()] * 100) # ========================================================== # Fonction de saisie de la taille du tableau # ========================================================== def saisie_taille(): # La variable test permet de contrôler # la validité de la taille saisie. test = False # Répéter la saisie tant que la taille # n'est pas comprise entre 2 et 14. while test == False: # Demander à l'utilisateur de saisir # la taille du tableau. n = int(input("donner n entre 2 et 14: ")) # Vérifier que la taille saisie # est comprise entre 2 et 14. if 2 <= n <= 14: # La taille saisie est correcte. # On affecte True à test afin de # terminer la boucle de saisie. test = True # Retourner la taille valide du tableau. return n # ========================================================== # Fonction de saisie de la valeur à rechercher # ========================================================== def saisie(): # Demander à l'utilisateur de saisir # la valeur qu'il souhaite rechercher # dans le tableau. x = int(input("donner la valeur à rechercher: ")) # Retourner la valeur saisie. return x # ========================================================== # Procédure de remplissage du tableau # ========================================================== def remplir(t, n): # Saisir le premier élément du tableau. # # Le premier élément n'a pas de précédent, # donc aucune comparaison n'est nécessaire. t[0] = int(input("donner un element du tableau : ")) # Parcourir les cases restantes du tableau # à partir de l'indice 1 jusqu'à l'indice n-1. for i in range(1, n): # La variable test permet de vérifier # si l'élément saisi respecte l'ordre croissant. test = False # Répéter la saisie tant que l'élément # saisi ne respecte pas l'ordre croissant. while test == False: # Demander à l'utilisateur de saisir # un élément du tableau. t[i] = int(input("donner un element du tableau : ")) # Vérifier que l'élément courant est # strictement supérieur à l'élément précédent. if t[i] > t[i - 1]: # L'élément saisi est correct. # L'ordre croissant est respecté. test = True # ========================================================== # Fonction de recherche dichotomique # ========================================================== def recherche(t, n, x): # a représente l'indice de début # de la zone dans laquelle on recherche x. # # Au début, la recherche commence # à la première case du tableau. a = 0 # b représente l'indice de fin # de la zone dans laquelle on recherche x. # # La dernière case utilisée possède # l'indice n - 1. b = n - 1 # resultat indique si la valeur x # a été trouvée dans le tableau. # # Au début de la recherche, x n'est pas encore trouvée. resultat = False # Répéter la recherche tant que : # # 1. x n'a pas encore été trouvée ; # 2. la zone de recherche n'est pas vide. # # La condition a <= b signifie qu'il reste # au moins une case à examiner. while (resultat == False) and (a <= b): # Calculer l'indice de l'élément situé # au milieu de la zone de recherche. # # // représente une division entière. p = (a + b) // 2 # Comparer la valeur recherchée x # avec l'élément situé au milieu du tableau. if x == t[p]: # x est égale à l'élément situé # à la position p. # # La valeur recherchée a donc été trouvée. resultat = True elif x > t[p]: # x est supérieure à l'élément du milieu. # # Le tableau est trié dans l'ordre croissant. # Tous les éléments situés à gauche de p # sont donc inférieurs à x. # # Il est inutile de continuer la recherche # dans cette partie. # # On déplace alors le début de la zone # de recherche après la position p. a = p + 1 elif x < t[p]: # x est inférieure à l'élément du milieu. # # Comme le tableau est trié dans l'ordre croissant, # tous les éléments situés à droite de p # sont supérieurs à x. # # Il est donc inutile de rechercher dans # cette partie. # # On déplace la fin de la zone de recherche # avant la position p. b = p - 1 # Retourner le résultat de la recherche. # # True : x a été trouvée. # False : x n'a pas été trouvée. return resultat # ========================================================== # Programme principal # ========================================================== # Appeler la fonction saisie_taille() # afin d'obtenir le nombre d'éléments # qui seront utilisés dans le tableau. n = saisie_taille() # Afficher un message indiquant # le début du remplissage du tableau. print("***Remplissage du tableau***") # Appeler la procédure remplir() # afin de saisir les n éléments du tableau. # # La procédure impose que les éléments soient # saisis dans l'ordre croissant. # # Exemple : # 2, 5, 8, 12, 17, 21, 30 remplir(t, n) # Appeler la fonction saisie() # afin de demander à l'utilisateur # la valeur qu'il souhaite rechercher. x = saisie() # ========================================================== # Recherche de la valeur # ========================================================== # Appeler la fonction recherche() # afin de rechercher x dans le tableau. # # La fonction recherche() retourne : # - True si x existe dans le tableau ; # - False si x n'existe pas dans le tableau. if recherche(t, n, x) == True: # Afficher un message indiquant # que la valeur recherchée a été trouvée. print(x, " est trouvé") else: # Afficher un message indiquant # que la valeur recherchée n'a pas été trouvée. print(x, " n'a pas été trouvé") |
Exécution programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
