Français
Menu

Structures de données et algorithmes

Quelle condition est nécessaire pour utiliser la recherche dichotomique, qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois ?

  1. ALe nombre de données doit être une puissance de deux
  2. BLes données doivent être triées selon la clé
  3. CLes données ne doivent pas contenir de valeurs en double
Afficher la réponse et l'explication

Réponse : B. Les données doivent être triées selon la clé

La recherche dichotomique utilise le résultat de la comparaison entre la cible et l'élément du milieu pour décider si la cible se trouve dans la première ou dans la seconde moitié, puis réduit l'intervalle de moitié. Cette conclusion n'est valable que parce que les données sont triées : on ne peut donc pas l'utiliser sur un tableau non trié. Le nombre de données n'a pas besoin d'être une puissance de deux : prendre le milieu égal à (bas + haut) ÷ 2 arrondi à l'entier inférieur fonctionne pour n'importe quelle taille. Les doublons ne posent pas non plus de problème : l'une des valeurs correspondantes est trouvée (trouver la première occurrence demande une petite étape supplémentaire).

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

Autres questions sur Structures de données et algorithmes

  1. On effectue une recherche dichotomique parmi 1000 valeurs distinctes triées par ordre croissant. Si une comparaison indique si les valeurs sont égales, plus petites ou plus grandes, quel est le nombre maximal de comparaisons, en comptant les recherches réussies comme infructueuses ?
  2. 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 ?
  3. 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 ?
  4. 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 ?
  5. 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 ?