ZAMYLA CHAN: La première chose que vous pourriez avis sur trouvaille est que nous avons déjà ont le code écrit pour nous. C'est ce qu'on appelle le code de distribution. Donc, nous ne sommes pas en train d'écrire notre propre coder à partir de zéro plus. Au contraire, nous sommes en remplissant les vides dans un code pré-existant. 

Le programme de find.c invite à numéros pour remplir la botte de foin, recherche dans le meule de foin pour une aiguille d'utilisateur soumis, et il le fait en appelant tri et de recherche, les fonctions définies dans helpers.c. Donc find.c est déjà écrit. Votre travail consiste à écrire des aides. 

Alors, que faisons-nous? Nous mettons en œuvre deux fonctions. Recherche, qui retourne true si une valeur se trouve dans la botte de foin, de retour false si la valeur est pas dans la botte de foin. Et puis nous sommes aussi implémenter le tri, qui trie le tableau des valeurs dites. Donc, nous allons aborder la recherche. 

Recherche est actuellement mis en œuvre comme une recherche linéaire. Mais vous pouvez faire beaucoup mieux que cela. La recherche linéaire est mis en œuvre dans O n temps, ce qui est assez lent, bien qu'il peut rechercher une liste donnée à lui. Votre travail consiste à mettre en œuvre la recherche binaire, qui a le temps d'exécution de O log n. C'est assez rapide. 

Mais il ya une stipulation. Recherche binaire ne peut chercher à travers des listes pré-triées. Pourquoi est-ce? Eh bien, regardons un exemple. Dans une série de valeurs, la botte de foin, nous allons être à la recherche une aiguille, et en ce Par exemple, le nombre entier 3. 

La façon dont la recherche binaire fonctionne est que on compare la valeur moyenne de le tableau à l'aiguille, de façon similaire comment nous avons ouvert un livre de téléphone au milieu la page à la Semaine 0. Ainsi, après la comparaison de la valeur moyenne de l'aiguille, vous pouvez jeter soit la gauche ou la partie droite du tableau en serrant vos limites. Dans ce cas, depuis le 3, notre aiguille, est inférieur à 10, la valeur moyenne, l' droit lié peut diminuer. 

Mais essayez de faire vos limites aussi serrée que possible. Si la valeur moyenne n'est pas l'aiguille, alors vous savez que vous n'avez pas besoin de inclure dans votre recherche. Ainsi, votre droit lié peut serrer la recherche bornes juste un tout petit peu plus, et ainsi de suite et ainsi de suite, jusqu'à ce que vous trouverez votre aiguille. 

Alors qu'est-ce pseudo Code ressembler? Eh bien, alors que nous sommes toujours à la recherche par le biais la liste et encore éléments à rechercher dans, nous prenons le milieu de la liste et les comparer valeur moyenne de notre aiguille. Si elles sont égales, alors cela signifie que nous avons trouvé l'aiguille, et nous pouvons return true. 

Dans le cas contraire, si l'aiguille est inférieure à la valeur moyenne, alors cela signifie que nous peut jeter la moitié droite et juste et chercher dans la partie gauche du tableau. Sinon, nous allons chercher la côté droit de la matrice. Et à la fin, si vous n'avez pas plusieurs éléments laissés à la recherche, mais vous n'ont pas encore trouvé votre aiguille, puis vous revenez faux. Parce que l'aiguille définitivement n'est pas dans la botte de foin. 

Maintenant, une chose intéressante à propos de cette pseudo code binaire de recherche est qu'il peut être interprété soit comme un processus itératif ou la mise en œuvre récursive. Donc, il serait récursif si vous appeliez la fonction de recherche dans la recherche fonctionner sur une ou l'autre moitié de la matrice. Nous allons couvrir la récursivité un peu plus tard dans le cours. Mais je ne sais que c'est une option si vous souhaitez essayer.