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.

À 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.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.