Optimalité de recherche binaire

Question

Cela peut être une question stupide, mais personne ne sait d'une preuve que la recherche binaire est asymptotiquement optimale? Autrement dit, si on nous donne une liste triée des éléments sur lesquels l'opération autorisée uniquement sur ces objets est une comparaison, comment peut-on prouver que la recherche ne peut se faire en o (n lg)? (C'est peu o logn, en passant.) Notez que je restreindre ce à des éléments où la seule opération a permis le fonctionnement est une comparaison, car il existe des algorithmes bien connus qui peuvent battre O (logn) sur l'attente si vous êtes autorisé à effectuer des opérations plus complexes sur les données (voir, par exemple, la recherche d'interpolation).

Answer 1

De :

• Le nombre de résultats possibles devrait être d'au moins O (n).
• Vous pouvez représenter les décisions effectuées par l'algorithme par des noeuds d'un « arbre de décision »: si les éléments se comparent plus il va sur le chemin, sinon il 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 y avoir au moins des noeuds O (n) dans l'arborescence.
• Chaque arbre à O (N) noeuds comprend au moins O (log N) niveaux.

Answer 2

La logique est simple. Supposons que nous avons éventail de n différents éléments triés.

1. Il sont 2 résultats possibles de 1 comparaison (premier élément est inférieur ou supérieur). Ainsi, si l'on est assez comparaison, n <= 2. Dans le cas contraire, si nous avons 3 éléments (a, b, c) et notre algorithme a 2 résultats possibles, l'un des 3 éléments ne seront jamais sélectionnés.
2. Il sont 4 résultats possibles de 2 comparaisons. Ainsi, si 2 comparaisons suffit, n <= 4.
3. De même, pour les comparaisons de k d'être assez n devrait être n <= 2^k.

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

Answer 3

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

Même si vous avez permis de faire quelques opérations supplémentaires, il est toujours pas assez -. Je suis sûr qu'il est possible de préparer la séquence des éléments où la recherche d'interpolation effectue 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. Probabilité de chaque ensemble de données entrantes est possible non uniforme.

La réponse est -. Tout dépend des connaissances supplémentaires que nous avons sur les ensembles de données entrants