Pourquoi est-il impossible de trouver une valeur spécifiée dans un tableau trié plus rapidement que O(log n) ?

Question

Je suis assez nouveau en informatique. En conclusion d'une conférence, mon professeur d'informatique AP a mentionné que le modèle de comparaison pour trouver une valeur spécifiée dans un tableau trié est un gros oméga (log n), c'est-à-dire (log n) , ce qui, si je comprends bien, signifie qu'il est impossible d'accomplir cela tâche plus rapide que O(log n) . Pourquoi est-ce?

Answer 1

Si vous ne connaissez pas les informations préliminaires sur la distribution des clés, votre recherche est en réalité O(log(n)), car à chaque comparaison, vous extrayez 1 bit d'information et réduisez la zone de recherche deux fois. Mais, pour des cas pratiques, vous pouvez rechercher dans un tableau trié beaucoup plus rapidement. Par exemple, voir la recherche d'interpolation , c'est juste O(log(log(n))).