[MUSIQUE JEU] 

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 dans un recherche linéaire, mais vous pouvez faire beaucoup mieux que cela. La recherche linéaire est mis en œuvre dans O de n temps, ce qui est assez lent. Bien, il peut rechercher une liste qui lui est donné. 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 dans cet exemple, le nombre entier de trois. 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 répertoire au milieu page en semaine zéro. 

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 trois ans, 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. Vous avez donc raison liée 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 que le pseudo ressemble? Eh bien alors que nous sommes toujours à la recherche par le biais la liste et ont encore des éléments à regarder dans, nous prenons le milieu de la liste, et comparer cette valeur moyenne à 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'avez pas encore trouvé votre aiguille, alors vous return false parce que l'aiguille n'est certainement pas dans la botte de foin. 

Maintenant, une chose intéressante à propos de cette pseudo- à la recherche binaire est qu'il peut être interprété comme étant 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 la bien sûr, mais je ne sais que c'est un option si vous souhaitez essayer. 

Maintenant regardons sorte. Trier prend un tableau et l'entier n, ce qui est la taille de la matrice. Maintenant, il existe différents types de toutes sortes, et vous pouvez regarder quelques-uns shorts pour des démonstrations et des explications. Le type de retour pour notre fonction de tri est vide. Cela signifie donc que nous n'allons pas à retourner n'importe quel tableau de genre. Nous allons en fait changer le très tableau qui a été adoptée en nous. 

Et c'est possible parce que les tableaux sont passés par référence en C. Maintenant, nous allons en savoir plus sur cela plus tard, mais la différence essentielle entre la réussite quelque chose comme un entier et le passage dans un tableau, c'est que lorsque vous passer à un nombre entier, C va juste faire une copie de cet entier et passer à la fonction. La variable d'origine ne sera pas modifié une fois que la fonction est terminée. Avec un tableau, d'autre part, c'est ne va pas faire une copie, et vous aurez être en fait l'édition du tableau elle-même. 

Donc, un type de tri est le genre de sélection. Le genre de sélection fonctionne en commençant par le début, puis vous parcourez plus et de trouver le plus petit élément. Et puis vous changez que la plus petite élément avec la première. Et puis vous passez à la deuxième élément , Trouver la prochaine plus petite élément, puis swap avec la second élément dans le tableau parce le premier élément est déjà trié. Et alors vous continuez pour chaque Elément à identifier le plus petit valeur et échangeant sur. 

Pour I est égale à 0, le premier élément à n moins 1, vous allez comparer chaque valeur suivante après cela et trouver l'indice de la valeur minimale. Une fois que vous trouverez l'indice de valeur minimale, vous pouvez échanger cette valeur de tableau I. minimum et réseau 

Un autre type de sorte que vous pouvez la mise en œuvre est tri à bulles. Ainsi bulle tri parcourt la liste on compare les éléments adjacents et permuter les éléments qui sont dans le mauvais ordre. Et de cette façon, le plus grand élément fera des bulles à la fin. Et la liste est triée fois plus éléments ont été échangés. 

Donc, ce sont deux exemples de tri algorithmes que vous pouvez mettre en œuvre pour le programme de recherche. Une fois que vous avez terminé de tri, et vous avez recherche effectuée, vous avez terminé. Mon nom est Zamyla, et c'est CS50. 

[MUSIQUE JEU]