Recherche binaire

Question

Alors, je veux comprendre plus sur la recherche binaire, parce que je ne comprends pas vraiment. recherche binaire nécessite une condition préalable qu'un tableau est trié. Je suis arrivé ce droit? Il semble comme une méthode doit vérifier cette condition préalable et lancer une exception si elle est pas remplie. Mais, pourquoi la vérification de la condition sine qua non d'une mauvaise idée?

Answer 1

Il est une mauvaise idée, car la vérification les données sont triées prend des mesures n. La recherche est tout sur les étapes de log(n).
Si vous allez vérifier, vous pourriez aussi bien faire une recherche linéaire.

Answer 2

Le point entier d'une recherche binaire est que, puisque les données sont déjà triées, vous pouvez trouver rapidement les informations que vous souhaitez.

Prenez l'annuaire téléphonique, qui est triée par nom.

Comment trouvez-vous quelqu'un dans l'annuaire téléphonique? Vous l'ouvrez une page que vous assumez sera proche de ce que vous voulez, puis commencer à tourner les pages.

Mais vous ne retournez une page à chaque fois, si vous avez manqué par beaucoup, vous retournez un tas de pages, puis enfin commencer en feuilletant un à la fois, jusqu'à ce que vous commencez à regarder une seule page.

est ce que recherche binaire fait. Puisque les données sont triées, il sait qu'il peut sauter beaucoup et faire un autre regard, et ça va se concentrer sur les informations que vous souhaitez.

Une recherche binaire fait 1 comparaison pour chaque nombre doublé d'articles. Ainsi, une collection de 1024 éléments, il faudrait environ 10 comparaisons, au plus, de trouver vos informations, ou tout au moins comprendre que ce n'est pas là.

Si vous, avant de lancer la recherche binaire réelle, est-ce une exécution complète par vérifier si les données sont triées, vous pourriez aussi bien le faire une analyse de l'information. Une pleine exécution à + la recherche binaire nécessiteront des opérations N + log2 N, donc pour 1024 éléments, il faudrait environ 1034 comparaisons, alors qu'un simple scan pour l'information sera en moyenne besoin de la moitié, soit 512.

Donc, si vous ne pouvez pas garantir que les données sont triées, vous ne devriez pas utiliser la recherche binaire, car il sera surclassé par un simple scan.

---

Modifier : Je vais dire cependant, vous pouvez ajouter un débogage seule étape de code pour vérifier, pour attraper des bugs dans le code qui est censé préparer les données pour la recherche binaire, mais savoir que, en raison de ce que j'ai écrit ci-dessus, cela va rendre le temps de fonctionnement total beaucoup plus élevé, donc en fonction de ce que vous voulez faire avec ce chèque, vous pourriez ou ne voulez pas ajouter. Mais il ne devrait pas être présent dans le code de libération.

Answer 3

Yep, une recherche binaire implique 0 (log N) étapes et la vérification de la séquence entière est triée implique 0 (n) étapes. De mon point de vue, il est bon de le vérifier en mode debug, et non lors de la libération.

Answer 4

recherche binaire suppose que les données d'entrée sont triés. Alors là, vous avez raison.

en vérification générale si les données sont triées un certain temps. Donc, l'exécution de cette avant chaque recherche serait la recherche vraiment inefficace.

Plus de détails.

On suppose que 'n' est le montant de vos données.

recherche binaire a besoin opération O(log(n)) dans le pire des cas pour trouver un élément. Faire en sorte que les données sont triées nécessite des opérations de O(n).

Donc, si nous allons vérifier préalable à chaque fois pour très grand n nous allons commencer à passer plus de temps sur la vérification préalable que de faire la recherche réelle.

Et il est pas si difficile de dire quand vous verrez un tel effet. Je viens calculé combien de temps vous passerez sur la pré-cheking par rapport à la recherche réelle

• Pour 1 élément que vous passez pas de temps de recherche.
• Pour 2 éléments que vous dépensez 50% sur la recherche.
• Pour 5 éléments que vous passez 46% sur la recherche
• Pour 20 éléments que vous dépensez 22% sur la recherche.
• Pour 100 éléments que vous dépensez 7% sur la recherche.

Et ainsi de suite. Dans tous les autres cas, le temps est de passer à l'enregistrement de condition préalable.

Answer 5

En plus de ce que tout le monde dit au sujet de temps d'exécution (O (n) pour vérifier tous les éléments, par rapport à O (log (n)) pour exécuter la recherche binaire.)

Je pense que vous comprenez mal l'idée d'une condition préalable. Conditions préalables et post-conditions sont un contrat. Si votre condition est vrai, et que vous exécutez votre algorithme, votre état de poste sera vrai. Si votre condition est fausse, alors vous faites aucune garantie sur la condition de poste.

Donc, fondamentalement, recherche binaire dit ceci: Si les données que vous me donnez est déjà triée, je peux vous dire la position d'une pièce spécifique de données, ou si elle n'est pas présent, en effectuant environ log contrôles (n) . Si les données ne sont pas triées, je ne fais aucune garantie quant à ma réponse.

Le travail que vous prend de votre condition préalable à votre post-condition si votre algorithme. Dans ce cas, la recherche binaire.

Answer 6

La question initiale suppose que vous utilisez une recherche binaire sur une collecte de données. Ce n'est pas toujours le cas. Plusieurs fois, vous essayez juste de calculer un nombre dans un certain intervalle.

Supposons que vous essayez de calculer le réglage optimal de la vitesse d'un ventilateur. Pour une raison quelconque, vous ne pouvez pas trouver une expression de forme fermée, de sorte que vous simuler le flux d'air à différents réglages de vitesse.

En supposant que le ventilateur peut fonctionner à une vitesse de 0rpm à 5000rpm, vous n'avez pas fait pour générer une liste de vitesses possibles. Vous trouvez que la moyenne du minimum et maximum précédent à chaque étape de la recherche binaire.