Français
Menu

Qu'est-ce que Recherche dichotomique (recherche binaire) ?

Méthode de recherche sur des données triées qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois. Elle trouve une valeur parmi n données en au plus ⌊log₂ n⌋ + 1 comparaisons, d'où une complexité en O(log n). Les données doivent être triées.

Nom japonais: 二分探索

« Recherche dichotomique (recherche binaire) » apparaît dans 7 questions d'entraînement réparties sur 3 thèmes, dont Structures de données et algorithmes, Conversion A/N et N/A, Développement logiciel et gestion de projet.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Recherche dichotomique (recherche binaire)

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

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 ?

  1. A10
  2. B32
  3. C500
Afficher la réponse et l'explication

Réponse : A. 10

Chaque comparaison réduit l'intervalle de recherche de moitié environ, et 2¹⁰ = 1024 ≥ 1000 : l'intervalle est donc épuisé en 10 comparaisons au plus (⌊log₂ 1000⌋ + 1 = 10). La complexité temporelle est en O(log n), et même 1 million de valeurs ne demandent que 20 comparaisons au plus. 32 correspond à √1000 ≈ 31,6, et 500 est proche de la moyenne d'une recherche linéaire (environ n/2). Il faut toutefois garder à l'esprit que la recherche dichotomique exige des données triées, et que le tri lui-même coûte O(n log n).

« Recherche dichotomique (recherche binaire) » dans les explications

Questions mentionnant « Recherche dichotomique (recherche binaire) » (7)

  1. 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 ?
  2. 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 ?
  3. 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 ?
  4. Après une version de micrologiciel dont on sait qu'elle fonctionne correctement, il y a 1000 commits, et le dernier commit présente un bogue. Le bogue a été introduit par un commit et se produit dans tous les commits suivants. Quand on identifie le commit fautif par recherche dichotomique, comme avec git bisect, combien de fois au maximum faut-il compiler et tester le micrologiciel ?
  5. Quel fonctionnement d'un CAN à approximations successives (SAR) est correct ?
  6. Combien de comparaisons un CAN SAR de N bits effectue-t-il fondamentalement par conversion ?
  7. Une recherche linéaire compare un à un, depuis le début, les éléments d'un tableau de 100 valeurs distinctes pour trouver une valeur cible. Si la cible se trouve toujours dans le tableau et a la même probabilité d'être à n'importe quelle position, quel est le nombre moyen de comparaisons ?

Termes associés

Tableau Complexité temporelle (notation grand O) CAN à approximations successives (SAR) Git Comparateur Suréchantillonnage Algorithme de Dijkstra Algorithme glouton (greedy) Arbre binaire de recherche (binary search tree) File d'attente

Retour au glossaire