Optimalité de la recherche binaire

Question

Cela peut être une question stupide, mais quelqu'un sait-il une preuve que la recherche binaire est asymptotiquement optimale? C'est-à-dire, si on nous donne une liste triée d'éléments où la seule opération permise sur ces objets est une comparaison, comment prouver que la recherche ne peut pas être faite dans o (lg n)? (C'est petit-o de lg n, soit dit en passant.) Notez que je restreins ceci aux éléments où la seule opération permise est une comparaison, car il y a des algorithmes bien connus qui peuvent battre O (lg n) en attente si vous êtes autorisé à effectuer des opérations plus complexes sur les données (voir, par exemple, une recherche par interpolation).

Answer 1

De here:

• Le nombre de résultats possibles devrait être d'au moins O (n).
• Vous pouvez représenter les décisions prises par l'algorithme par les nœuds d'un «arbre de décision»: si les éléments se comparent plus grand, alors il continue, sinon ça va dans l'autre sens. Les nœuds de l'arbre sont les états de l'algorithme et les feuilles sont les résultats. Il devrait donc y avoir au moins O (n) nœuds dans l'arbre.
• Chaque arbre sur les nœuds O (n) a au moins O (log N) niveaux.

Answer 2

La logique est simple. Supposons que nous ayons un tableau de n éléments triés différents.

1. Il sont 2 résultats possibles de 1 comparaison (premier élément est inférieur ou supérieur). Ainsi, si une comparaison est suffisante, n <= 2. Sinon, si nous avons 3 éléments (a, b, c) et que notre algorithme a 2 résultats possibles, l'un des 3 éléments ne sera jamais sélectionné.
2. Il y a 4 résultats possibles de 2 comparaisons. Ainsi, si 2 comparaisons sont suffisantes, n <= 4.
3. De même, pour k les comparaisons pour être suffisamment n doivent être n <= 2^k.

Inversez la dernière inégalité et vous aurez un logarithme: k >= log(2, n).

Answer 3

Comme décrit Nikita il est impossible d'avoir quelque chose toujours mieux que O (log n).

Même si vous avez autorisé certaines opérations supplémentaires, ce n'est pas encore suffisant - je suis sûr qu'il est possible de préparer une séquence d'éléments où la recherche par interpolation sera pire que la recherche binaire.

On peut dire la recherche d'interpolation est mieux seulement parce que:

1. Nous considérons la performance moyenne, pas le pire des cas.
2. La probabilité de chaque jeu de données entrant possible est non uniforme.

Donc la réponse est - tout dépend de la connaissance supplémentaire que nous avons sur les ensembles de données entrants.