Chapitre 5 : recherche dichotomique
Joan Clarke est une cryptologue britannique. Elle est principalement connue pour sa participation au décryptage de la machine Enigma qui codait les communications chiffrées du Troisième Reich. Elle est recrutée en juin 1940 par son ancien superviseur académique Gordon Welchman pour travailler au Government Code and Cypher School (GC&CS), à Bletchley Park, au sein de la Hutte 8, chargée du décryptage des codes de la Kriegsmarine, où elle est par ailleurs la seule femme. Elle devient rapidement l'une des meilleures parmi les pratiquants du banburismus, une méthode de cryptanalyse développée par Alan Turing, dont elle est l'une des plus proches amies et très brièvement la fiancée.
On a vu précédemment comment rechercher un élément dans un tableau. Si celui-ci n'est pas trié, cette recherche nous oblige à parcourir l'intégralité du tableau, que l'élément soit présent ou non. En revanche, si celui-ci est trié, la recherche peut être beaucoup plus efficace comme nous allons le voir.
La recherche dichotomique, ou recherche par dichotomie (en anglais : binary search), est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié.
Le but de ce chapitre est de présenter l'algorithme de recherche dichotomique et de l'appliquer à quelques exemples simples.
On propose le déroulé suivant :
- un point de cours présentant le principe général de l'algorithme, ses spécifications, sa preuve et sa complexité dans le pire des cas ;
- des exercices d'entraînement sur la recherche dichotomique.
Afficher le cours
Afficher les exercices
Il n'y a pas de ressources à télécharger.