Recherche dichotomique dans un tableau - Algorithme & programme Python

Bonjour à tous et bienvenue dans cette nouvelle vidéo d'algorithmique où nous allons traiter l'exercice suivant: Écrire un algorithme qui permet de trouver l'indice d'un élément dans un tableau d'entiers trié en effectuant une recherche dichotomique. De la manière la plus basique qui soit, si on souhaite rechercher l'indice d'un élément dans un tableau déjà trié, alors on parcourt celui-ci du début à la fin en comparant chaque élément rencontré avec l'élément recherché. À titre d'exemple, imaginons que l'on dispose d'un tableau d'entiers identifié par tab et qui contient les entrées suivantes: 10, 15, 19, 23, 32, 65, 68 et 99. Si on recherche l'indice de l'élément 32, alors on commence par le premier indice qui vaut 0 et qui contient la valeur 10. Puisque cette entrée est différente de l'élément recherché, alors on passe à l'indice suivant qui vaut 1. Dans cette position il y a l'élément 15 qui est encore différent de 32. On continue ainsi jusqu'à ce qu'on atteigne l'indice 4 qui contient l'entier 32 qui correspond à l'élément recherché, et on cesse le parcours du tableau. Donc la position de l'élément 32 vaut 4. Alors, au bout de 5 itérations nous avons fini par trouver l'indice de l'élément recherché, ce qui est acceptable. Cependant, si le tableau était plus volumineux et que par hasard l'élément recherché est situé vers la fin, alors on serait obligé d'exécuter beaucoup plus d'itérations, qui ne serait sans doute pas tolérable. Heureusement, la recherche par dichotomie semble être l'une des solutions les plus optimisées dans ce genre de situation. En effet, le principe de la recherche dichotomique repose sur le fait de rechercher l'élément en question par paliers, en réduisant l'intervalle parcouru de moitié à chaque itération. Par conséquent, le nombre maximal d'itérations à exécuter établit une relation logarithmique avec la taille du tableau à parcourir, autrement dit, Le nombre maximal d'itérations baisse considérablement si on compare avec la première méthode. La recherche dichotomique se passe de la manière suivante: on commence par établir l'intervalle de recherche initial et qui couvre le tableau entier. On précise alors le début de l'intervalle à l'indice 0 et la fin de celui-ci à l'indice 7. Ensuite, nous calculons l'indice de la case du milieu de l'intervalle courant en utilisant la formule indice de début+ indice de fin divisé par 2. Autrement dit, 0+ 7 divisé par 2. Vu que l'indice doit être un entier, alors on procède à la division entière, ce qui donne 3. On compare alors l'élément recherché qui vaut 32 avec la valeur contenue dans la case du milieu indexée par 3. Cette valeur vaut 23. Puisque 23 est inférieur à 32, alors on peut en déduire que la case qui contient 32 se trouve dans l'intervalle situé à droite de la case 3. Maintenant, on change l'intervalle de recherche en précisant que le début vaut l'indice 4. C'est-à-dire l'indice de la case du milieu calculé précédemment+ 1, et on conserve la fin de l'intervalle tel qu'il est, c'est-à-dire l'indice 7. On recommence le traitement précédent en calculant l'indice du milieu qui vaut la division entière de 4+ 7 par 2, c'est-à-dire 5. On compare l'élément recherché qui vaut 32 avec l'élément contenu dans la case 5 et qui vaut 65. Vu que 65 est supérieur à 32, alors on sait que l'élément recherché est situé à gauche de la case 5. On spécifie le nouvel intervalle de recherche en précisant que la fin vaut l'indice 4, alors que le début reste inchangé, c'est-à-dire 4. On recalcule l'indice de la case du milieu qui vaut la partie entière de 4+ 4 sur 2, c'est-à-dire 4. On compare 32 avec l'élément contenu dans la case 4 qui vaut 32 aussi, ce qui veut dire que la position de l'élément recherché a été trouvée et vaut 4, et la recherche est aussitôt interrompue. Bien entendu, L'utilité de cette méthode de recherche se manifeste quand on a affaire à des tableaux volumineux. Vu le traitement demandé, il est évident qu'on aura affaire à un traitement itératif. Certains programmeurs préfèrent appréhender ce genre d'itération à l'aide d'une fonction récursive, mais je préfère utiliser l'une des 3 structures itératives classiques TantQue, Pour et Répéter. On peut déjà exclure la boucle Pour car le nombre de fois que l'on changera d'intervalle de recherche n'est pas connu à l'avance. Il nous reste donc la structure TantQue et la structure Répéter. La manière avec laquelle le traitement se présente nous mène à privilégier la structure Répéter, mais vu que l'on implémentera notre algorithme en programme Python et que celui-ci ne dispose pas de la structure Répéter ou Do While, alors on va utiliser la boucle TantQue. Dans cet algorithme on aura besoin des variables suivantes: tab qui est un tableau d'entiers trié qui renferme éventuellement l'élément que l'on recherche. Lm qui représente l'élément à rechercher, Deb et Fin qui représentent respectivement le début et la fin de l'intervalle de recherche, ces deux variables changeront de valeur afin de réduire de moitié l'intervalle de recherche à chaque itération, m qui représente l'indice de la case du milieu de l'intervalle établi, Trouvé qui est un booléen auquel on affectera la valeur VRAI si l'élément recherché est trouvé. Cette variable sera initialisée avec la valeur FAUX. Remarquez l'absence de E accent dans cet identifiant afin de se conformer aux règles de nommage des variables. Toutes les variables de cet algorithme seront de type entier, à l'exception de la variable trouvé qui est de type booléen. Je propose l'algorithme suivant: On commence par initialiser et trier le tableau tab. Cet ensemble d'instructions a été déclaré à l'aide d'un commentaire pour dire que ce tableau est déjà prêt à l'emploi. Je vous invite quand même à regarder l'exercice où j'ai traité le tri d'un tableau à l'aide de la méthode triabulle. Pour cet algorithme, on considère que le premier indice vaut 0. Ensuite, on demande à l'utilisateur de préciser la valeur de l'élément à rechercher, que l'on récupère juste après dans la variable lm. Maintenant, on doit délimiter l'intervalle de recherche dans le tableau. Dans un premier temps, l'intervalle englobe le tableau entier. On initialise donc la variable Deb à 0 pour dire que l'intervalle commence à l'indice 0 et la variable Fin à longueur tab- 1 pour dire que ce même intervalle finit au dernier indice du tableau. Ensuite, on calcule l'indice de la case du milieu m qui vaut la partie entière de Deb+ Fin divisé par 2. Il s'agit là d'une division entière. Quant à la variable trouvé, on l'initialise avec la valeur Faux pour dire qu'initialement l'élément recherché n'est pas encore trouvé. On procède ensuite à un traitement itératif à l'aide de la structure TantQue. En effet, tant que début est inférieur ou égal à fin, on procède au traitement itératif. N'oubliez pas que les variables qui vont faire office de début et fin changeront de valeur à chaque itération de telle sorte à rétrécir l'intervalle de recherche. Dans la boucle TantQue, on vérifie si la valeur contenue dans la case du milieu est égale à l'élément recherché. Si c'est le cas, alors l'élément a été trouvé. On change alors la valeur de la variable trouvé en Vrai, puis on met fin à la boucle TantQue à l'aide du mot-clé Break. Sinon, c'est-à-dire si la valeur de la case du milieu est différente de l'élément recherché, alors il faut réduire l'intervalle de recherche, soit en faisant avancer la valeur de début, ou en faisant reculer la valeur de fin. On doit alors déterminer de quel côté est situé l'élément que l'on recherche par rapport à la case du milieu. On doit par conséquent procéder à un autre traitement conditionnel. En effet, si la valeur de la case du milieu est supérieure à la valeur de l'élément recherché, alors ce dernier est forcément situé dans la première moitié de l'intervalle courant. On laisse alors le début de l'intervalle tel qu'il est et on réduit la valeur de fin de telle sorte à ce qu'elle soit égale à m-1, c'est-à-dire l'indice de la case située juste avant celle du milieu de l'intervalle précédent. Sinon, c'est-à-dire si l'élément recherché se trouve dans la deuxième moitié de l'intervalle, alors on laisse la valeur de fin telle qu'elle est et on fait avancer la valeur de début de telle sorte à ce qu'elle soit égale à m+1, ce qui veut dire l'indice de la case située juste après celle du milieu de l'intervalle précédent. Avant de recommencer la boucle, on recalcule l'indice de la case du milieu du nouvel intervalle par la même formule et on refait le traitement. À la sortie de la boucle, on vérifie si la variable trouvé vaut VRAI, ce qui signifie que l'élément recherché a été trouvé. Si c'est le cas, on affiche sa position, ou son indice, dans le tableau. Remarquez encore l'échappement des apostrophes. Sinon, c'est-à-dire si la valeur de la variable trouvée demeure FAUX, comme elle a été initialisée avant d'entrer dans la boucle, alors on affiche que l'élément est introuvable et on met fin à l'algorithme. Si vous êtes un peu confus face à ce traitement alors pas d'inquiétude, il vous suffit de prendre un crayon et un papier, dessiner les cases du tableau en leur affectant les indices appropriés et suivre le raisonnement en faisant les calculs décrits dans l'algorithme, vous vous rendrez compte que ce n'est pas aussi compliqué qu'il n'y paraît. Maintenant, nous allons implémenter notre algorithme en programme à l'aide du langage Python. On commence par déclarer notre tableau tab. En Python, on appelle cette structure une liste. C'est semblable aux tableaux dans d'autres langages de programmation. Ici, je vais fixer la valeur de lm dans le programme lui-même, car dans l'algorithme nous avons invité l'utilisateur à saisir cette valeur. On mettra donc lm= 32. Puis on va initialiser les valeurs de début et fin. Début vaut la valeur 0 pour dire le premier indice et fin vaut la longueur du tableau moins 1, c'est-à-dire le dernier indice. Et la position de la cellule du milieu est calculée avec la formule Début+ Fin/ 2. Il s'agit là d'une division entière. Puis on initialise la variable Trouvé avec la valeur booléenne False. Maintenant on va procéder au traitement itératif. Tant que Début est inférieur ou égal à Fin, on vérifie si la cellule du milieu contient la valeur recherchée. Si c'est le cas, alors on change la valeur de trouvé en True, puis on met fin à la boucle. Sinon, alors on va rétrécir l'intervalle de recherche. Au lieu de mettre else puis un autre bloc, en Python on dispose de la structure elif. Qui est une combinaison de else if. Puis on va énoncer la condition pour dire si la valeur de la case du milieu est supérieure à la valeur recherchée, dans ce cas on fera reculer la position de fin. Sinon, on fera avancer la position de début. Puis on recalcule la nouvelle position du milieu. On sort de la boucle et on vérifie la valeur de trouvé. If trouvé signifie si trouvé est égal à True. Alors on va afficher l'indice de l'élément trouvé. En Python, l'échappement des caractères spéciaux se fait avec antislash. Et n'oublie pas de caster la variable m en chaîne de caractères parce qu'à l'origine il s'agit d'un entier que l'on ne peut pas concaténer. Sinon, ça veut dire que l'élément n'a pas été trouvé, on va mettre élément introuvable. Exécutons. Donc ça nous affiche l'indice de l'élément recherché est 4. Il s'agit bien de la position 4 dans ce cas. Changeons de valeur, par exemple 99. Dans ce cas ça m'affiche la position 7, ça veut dire la dernière position du tableau. Maintenant on va mettre la valeur 100. C'est une valeur qui ne figure pas dans le tableau. Et ça m'affiche élément introuvable. Alors on estime que notre programme fonctionne bien. Merci pour votre attention et à la vidéo prochaine.