Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Recherche dichotomique
Résumé
La recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.
Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau. Il y a de nombreuses structures spécialisées (comme les tables de hachage) qui peuvent être recherchées plus rapidement, mais la recherche dichotomique s'applique à plus de problèmes.
On peut illustrer l'intérêt de la recherche dichotomique par l'exemple du jeu suivant.
A et B jouent au jeu suivant : A choisit un nombre entre 1 et 20, et ne le communique pas à B, B doit trouver ce nombre en posant des questions à A dont les réponses ne peuvent être que « Non, plus grand », « Non, plus petit » ou « Oui, trouvé ». B doit essayer de poser le moins de questions possible.
Une stratégie pour B est d'essayer tous les nombres, mais il peut aller plus rapidement comme le montre le scénario suivant :
A choisit 14 et attend les questions de B :
B sait que le nombre est entre 1 et 20 ; au milieu se trouve 10 (ou 11), B demande donc : « Est-ce que le nombre est 10 ? ». A répond « Non, plus grand ».
B sait maintenant que le nombre est entre 11 et 20 ; au milieu se trouve 15 (ou 16), il demande donc : « Est-ce que le nombre est 15 ? » A répond « Non, plus petit »
Et ainsi de suite : « Est-ce 12 ? » (12 < (11+14)÷2 < 13), « Non, plus grand », « Est-ce 13? » (13 < (13+14)÷2 < 14), « Non, plus grand », « Est-ce bien 14 ? », « Oui, trouvé »
B a trouvé le nombre choisi par A en seulement 5 questions.
L'algorithme est le suivant :
Trouver la position la plus centrale du tableau (si le tableau est vide, sortir).
Comparer la valeur de cette case à l'élément recherché.
Si la valeur est égale à l'élément, alors retourner la position, sinon reprendre la procédure dans la moitié de tableau pertinente.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (30)
CS-450: Algorithms II
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
FIN-414: Optimization methods
This course presents the problem of static optimization, with and without (equality and inequality) constraints, both from the theoretical (optimality conditions) and methodological (algorithms) point
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a