QCM : Recherche dichotomique — 10 questions

Explication

Le déroulement correct examine successivement 11, 18, puis 14. L’indice 5 correspond à la sixième position dans une liste dont le premier élément possède l’indice 0 ; la valeur 14 n’est donc pas à la quatrième position.

Explication

La recherche dichotomique est une méthode efficace qui fonctionne uniquement sur une liste triée en divisant l'espace de recherche par deux à chaque étape. Contrairement à la recherche linéaire, elle élimine rapidement la moitié des éléments à chaque étape, ce qui la rend très performante.

Explication

Dans cette liste, la valeur centrale initiale est 11, puis la recherche examine 18 avant d’atteindre 14. La valeur 14 se trouve à l’indice 5, même si elle occupe la sixième position lorsque l’on compte à partir de un.

Explication

Après avoir examiné le milieu de la liste, on compare la valeur centrale à la valeur recherchée pour décider de la moitié à conserver. La division en deux parts est une étape précédente, pas après la comparaison.

Explication

La valeur centrale guide le choix de la moitié à conserver : une valeur recherchée plus petite conduit vers la gauche, tandis qu’une valeur plus grande conduit vers la droite. La recherche s’arrête lorsque la valeur est trouvée ou que l’intervalle est épuisé.

Explication

La fonction trouve_dicho a pour rôle de localiser la position d'une valeur spécifique dans une liste triée en utilisant la recherche dichotomique. Elle ne trie pas la liste ni ne compare toutes les valeurs, mais divise efficacement l'espace de recherche.

Explication

La recherche dichotomique s’applique à une liste triée et réduit l’intervalle d’environ moitié à chaque étape. Elle examine la valeur centrale, puis conserve la moitié correspondant à la comparaison avec la valeur recherchée.

Explication

La formule $k = \log_2(n)$ est utilisée pour estimer le nombre d'itérations nécessaires dans le pire des cas de la recherche dichotomique. Elle indique que le nombre d'étapes est proportionnel au logarithme en base 2 de la taille initiale de la liste, ce qui montre l'efficacité de l'algorithme.

Explication

La recherche dichotomique divise la liste en deux à chaque étape, ce qui lui confère une complexité logarithmique $O(\text{log}_2 N)$, contrairement à la recherche linéaire qui parcourt chaque élément, avec une complexité linéaire $O(N)$. La différence principale réside dans la méthode de division et la nécessité de trier la liste pour la dichotomique.

Explication

John von Neumann est souvent crédité pour avoir conceptualisé la recherche dichotomique, une méthode fondamentale en informatique. Alan Turing a contribué à la théorie de la calculabilité, mais pas spécifiquement à cette méthode.