L'algorithme de recherche dichotomique dans un tableau trié
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Comprendre l’algorithme de recherche dichotomique dans un tableau trié.
- Étudier la terminaison et la correction de cet algorithme.
- La recherche dichotomique est un algorithme de recherche qui permet de déterminer la position d’un élément dans un tableau trié. Cet algorithme compare la valeur recherchée à la valeur du milieu du tableau.
- Un variant de boucle est une valeur entière qui répond à deux critères. La valeur doit être positive ou nulle, et être strictement décroissante. Ce variant permet de prouver la terminaison, c’est-à-dire de vérifier que le programme s’arrêtera.
- Un invariant de boucle est une proposition qui doit être vraie à chaque itération de l’algorithme. Cet invariant permet de prouver la correction, c’est-à-dire de vérifier que le programme retournera bien ce que l’on veut.
- Parcourir un tableau.
- Utiliser les structures conditionnelles.
On va considérer un tableau trié dans l’ordre croissant, mais tout ce qui suit fonctionne également pour un tri dans l’ordre décroissant.
Cet algorithme compare la valeur recherchée à la valeur du milieu du tableau.
- Si c’est la valeur recherchée, on s’arrête et on retourne sa position.
- Si cette valeur est plus petite, alors la valeur recherchée est située dans la partie gauche du tableau, sinon elle est dans la partie droite.
On répète le procédé de comparaison jusqu’à ce que l’on obtienne la valeur recherchée, ou jusqu’à ce que l’on ait réduit l’intervalle de recherche à un intervalle vide : cela signifie que la valeur recherchée n’est pas présente dans le tableau.
À chaque étape, la zone de recherche de la valeur est divisée par deux.
On va écrire un programme Python qui retourne la position de l’élément x si celui-ci se trouve dans le tableau, et None si l’élément ne s’y trouve pas.
Le programme devra retourner 1 pour x=5.
Le programme devra retourner None pour x=90.
On utilise deux variables gauche et droite pour écrire le programme qu’on initialise pour délimiter l’intégralité du tableau.
En Python, la fonction dichotomie(t, v) implémente la recherche dichotomique de la valeur v par rapport au tableau t.
| def dichotomie(t, v): | On définit la fonction dichotomie. |
| gauche = 0 | On initialise la variable gauche. |
| droite = len(t) - 1 | On initialise la variable droite. |
| while gauche <= droite: | Tant que l’indicateur droite est supérieur à gauche, on continue. |
| milieu = (gauche + droite) // 2 | On prend l’indice du milieu. |
| if t[milieu] == v: | Si la valeur recherchée v est égale à la valeur du milieu du tableau, |
| return milieu | alors on retourne l’indice. |
| elif t[milieu] > v: | Si la valeur recherchée v est supérieure à la valeur du milieu du tableau, |
| droite = milieu - 1 | alors on décrémente l’indice droite. |
| else: | Sinon, |
| gauche = milieu + 1 | on incrémente l’indice gauche. |
| return None | On retourne None. |
L’algorithme de la recherche dichotomique contient une boucle non bornée while, il faut s’assurer que cette boucle s’arrête.
On doit pour cela trouver un variant de boucle.
La valeur doit :
- être positive ou nulle ;
- être strictement décroissante.
Si on trouve un variant de boucle, on va obligatoirement sortir de la boucle au bout d’un nombre fini d’étapes.
On va montrer que la valeur « droite – gauche » décroit strictement à chaque itération.
- Si t[milieu] == v, alors on sort de la boucle.
- Si t[milieu] > v, alors gauche devient gauche+1, donc le variant décroit strictement (la gauche du tableau se rapproche de la droite).
- Si t[milieu] < v, alors droite devient droite–1, donc le variant décroit strictement (la droite du tableau se rapproche de la gauche).
On a donc bien un variant de boucle, le programme se termine car la boucle se termine toujours.
Pour prouver la correction de cet algorithme, on va utiliser la technique de l’invariant de boucle.
Un invariant de boucle peut être : « Si v (la valeur recherchée) est dans t (le tableau), son indice est compris entre gauche et droite. »
|
Démonstration de la correction
Si la propriété est vraie en entrée de boucle, alors il n’y a que trois possibilités.
On a donc bien un invariant de boucle et l’algorithme fait bien ce que l’on veut dans le cas où la recherche aboutit. |
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Résoudre un problème avec un algorithme glouton
NSI
Écrire un entier positif dans une base donnée
NSI
Passer de la représentation d'une base à une autre
NSI
Comprendre les bases de la représentation binaire
NSI
Effectuer des opérations en binaire
NSI
Utiliser la méthode du complément à 2 en binaire
NSI
Représenter les nombres réels en binaire
NSI
Comprendre les booléens
NSI
Utiliser les opérateurs booléens élémentaires
NSI
Obtenir une table de vérité d'une expression booléenne complexe
NSI
Représenter un texte en utilisant différents encodages
Fermer
Accédez gratuitement à
