Français
Menu

Structures de données et algorithmes

Une recherche dichotomique cherche 38 dans le tableau croissant a[0] à a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. L'intervalle de recherche commence avec lo = 0 et hi = 9, et la position du milieu vaut (lo + hi) ÷ 2 arrondi à l'entier inférieur. Quelle liste donne, dans l'ordre, les éléments comparés à 38 ?

  1. A23, 38
  2. B31, 52, 45, 38
  3. C23, 45, 31, 38
Afficher la réponse et l'explication

Réponse : C. 23, 45, 31, 38

D'abord, (0 + 9) ÷ 2 = 4 : 38 est comparé à a[4] = 23 ; 38 est plus grand, donc lo = 5. Ensuite, (5 + 9) ÷ 2 = 7 : il est comparé à a[7] = 45 ; 38 est plus petit, donc hi = 6. Puis (5 + 6) ÷ 2 = 5 donne a[5] = 31, donc lo = 6, et enfin a[6] = 38 correspond. Cela fait 4 comparaisons, le maximum pour 10 éléments, ⌊log₂ 10⌋ + 1 = 4. L'ordre 31, 52, 45, 38 résulte d'un arrondi du milieu à l'entier supérieur, ce qui n'est pas la règle donnée dans la question.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. On trie par ordre croissant le tableau 5, 3, 8, 1, 4 avec le tri à bulles. Quel est le tableau après une passe, au cours de laquelle les éléments voisins sont comparés du début jusqu'à la fin et échangés chaque fois que celui de gauche est le plus grand ?
  2. On trie par ordre croissant le tableau 29, 10, 14, 37, 13 avec le tri par sélection, qui cherche le minimum de la partie non triée et l'échange avec le premier élément de cette partie. Quel est le tableau après deux répétitions de cette étape ?
  3. On trie par ordre croissant un tableau de 10 éléments avec le tri par insertion. Chaque élément à partir du deuxième est extrait et comparé aux éléments situés à sa gauche, en commençant par son voisin de gauche, jusqu'à trouver un élément inférieur ou égal ou jusqu'à atteindre le début. Combien de comparaisons sont effectuées quand le tableau est déjà dans l'ordre croissant, et quand il est dans l'ordre décroissant ?
  4. Quel algorithme de tri a une complexité temporelle en O(n log n) même dans le pire cas et trie presque sans mémoire supplémentaire, comme un tableau de travail ?
  5. Les enregistrements (nom, note) (A, 80), (B, 70), (C, 80), (D, 70) sont dans cet ordre. Si on les trie par note croissante avec un tri stable, dans quel ordre les noms apparaissent-ils ?