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 ?

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