1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: La première chose que vous pourriez
avis sur trouvaille est que nous avons déjà

3
00:00:13,120 --> 00:00:14,520
ont le code écrit pour nous.

4
00:00:14,520 --> 00:00:16,219
C'est ce qu'on appelle le code de distribution.

5
00:00:16,219 --> 00:00:19,060
Donc, nous ne sommes pas en train d'écrire notre propre
coder à partir de zéro plus.

6
00:00:19,060 --> 00:00:23,870
Au contraire, nous sommes en remplissant les vides
dans un code pré-existant.

7
00:00:23,870 --> 00:00:28,860
>> Le programme de find.c invite à numéros
pour remplir la botte de foin, recherche dans le

8
00:00:28,860 --> 00:00:33,260
meule de foin pour une aiguille d'utilisateur soumis,
et il le fait en appelant tri et de

9
00:00:33,260 --> 00:00:36,660
recherche, les fonctions définies
dans helpers.c.

10
00:00:36,660 --> 00:00:38,740
Donc find.c est déjà écrit.

11
00:00:38,740 --> 00:00:41,840
Votre travail consiste à écrire des aides.

12
00:00:41,840 --> 00:00:42,940
>> Alors, que faisons-nous?

13
00:00:42,940 --> 00:00:45,270
Nous mettons en œuvre deux fonctions.

14
00:00:45,270 --> 00:00:50,110
Recherche, qui retourne true si une valeur
se trouve dans la botte de foin, de retour

15
00:00:50,110 --> 00:00:52,430
false si la valeur est
pas dans la botte de foin.

16
00:00:52,430 --> 00:00:59,060
Et puis nous sommes aussi implémenter le tri,
qui trie le tableau des valeurs dites.

17
00:00:59,060 --> 00:01:01,120
Donc, nous allons aborder la recherche.

18
00:01:01,120 --> 00:01:04,550
>> Recherche est actuellement mis en œuvre
comme une recherche linéaire.

19
00:01:04,550 --> 00:01:06,620
Mais vous pouvez faire beaucoup mieux que cela.

20
00:01:06,620 --> 00:01:11,610
La recherche linéaire est mis en œuvre dans O n
temps, ce qui est assez lent, bien qu'il

21
00:01:11,610 --> 00:01:14,920
peut rechercher une liste donnée à lui.

22
00:01:14,920 --> 00:01:21,190
Votre travail consiste à mettre en œuvre la recherche binaire,
qui a le temps d'exécution de O log n.

23
00:01:21,190 --> 00:01:22,200
C'est assez rapide.

24
00:01:22,200 --> 00:01:24,240
>> Mais il ya une stipulation.

25
00:01:24,240 --> 00:01:28,910
Recherche binaire ne peut chercher
à travers des listes pré-triées.

26
00:01:28,910 --> 00:01:31,450
Pourquoi est-ce?

27
00:01:31,450 --> 00:01:33,690
Eh bien, regardons un exemple.

28
00:01:33,690 --> 00:01:37,350
Dans une série de valeurs, la botte de foin,
nous allons être à la recherche

29
00:01:37,350 --> 00:01:41,510
une aiguille, et en ce
Par exemple, le nombre entier 3.

30
00:01:41,510 --> 00:01:45,220
>> La façon dont la recherche binaire fonctionne est que
on compare la valeur moyenne de

31
00:01:45,220 --> 00:01:49,430
le tableau à l'aiguille, de façon similaire comment
nous avons ouvert un livre de téléphone au milieu

32
00:01:49,430 --> 00:01:51,720
la page à la Semaine 0.

33
00:01:51,720 --> 00:01:55,710
Ainsi, après la comparaison de la valeur moyenne de
l'aiguille, vous pouvez jeter soit la

34
00:01:55,710 --> 00:01:59,620
gauche ou la partie droite du tableau
en serrant vos limites.

35
00:01:59,620 --> 00:02:04,450
Dans ce cas, depuis le 3, notre aiguille, est
inférieur à 10, la valeur moyenne, l'

36
00:02:04,450 --> 00:02:07,060
droit lié peut diminuer.

37
00:02:07,060 --> 00:02:09,470
>> Mais essayez de faire vos limites
aussi serrée que possible.

38
00:02:09,470 --> 00:02:12,690
Si la valeur moyenne n'est pas l'aiguille,
alors vous savez que vous n'avez pas besoin de

39
00:02:12,690 --> 00:02:14,070
inclure dans votre recherche.

40
00:02:14,070 --> 00:02:18,390
Ainsi, votre droit lié peut serrer la
recherche bornes juste un tout petit peu plus,

41
00:02:18,390 --> 00:02:22,840
et ainsi de suite et ainsi de suite, jusqu'à ce que
vous trouverez votre aiguille.

42
00:02:22,840 --> 00:02:24,580
>> Alors qu'est-ce pseudo
Code ressembler?

43
00:02:24,580 --> 00:02:28,980
Eh bien, alors que nous sommes toujours à la recherche par le biais
la liste et encore

44
00:02:28,980 --> 00:02:33,540
éléments à rechercher dans, nous prenons le milieu
de la liste et les comparer

45
00:02:33,540 --> 00:02:36,020
valeur moyenne de notre aiguille.

46
00:02:36,020 --> 00:02:38,380
Si elles sont égales, alors cela signifie que nous avons
trouvé l'aiguille, et nous pouvons

47
00:02:38,380 --> 00:02:40,160
return true.

48
00:02:40,160 --> 00:02:43,940
>> Dans le cas contraire, si l'aiguille est inférieure à
la valeur moyenne, alors cela signifie que nous

49
00:02:43,940 --> 00:02:48,350
peut jeter la moitié droite et juste
et chercher dans la partie gauche du tableau.

50
00:02:48,350 --> 00:02:51,860
Sinon, nous allons chercher la
côté droit de la matrice.

51
00:02:51,860 --> 00:02:55,470
Et à la fin, si vous n'avez pas
plusieurs éléments laissés à la recherche, mais vous

52
00:02:55,470 --> 00:02:58,030
n'ont pas encore trouvé votre aiguille,
puis vous revenez faux.

53
00:02:58,030 --> 00:03:02,960
Parce que l'aiguille définitivement
n'est pas dans la botte de foin.

54
00:03:02,960 --> 00:03:06,200
>> Maintenant, une chose intéressante à propos de cette pseudo
code binaire de recherche est qu'il peut

55
00:03:06,200 --> 00:03:11,000
être interprété soit comme un processus itératif
ou la mise en œuvre récursive.

56
00:03:11,000 --> 00:03:14,900
Donc, il serait récursif si vous appeliez
la fonction de recherche dans la recherche

57
00:03:14,900 --> 00:03:18,400
fonctionner sur une ou l'autre moitié de la matrice.

58
00:03:18,400 --> 00:03:20,750
Nous allons couvrir la récursivité un peu
plus tard dans le cours.

59
00:03:20,750 --> 00:03:23,210
Mais je ne sais que c'est une option
si vous souhaitez essayer.

60
00:03:23,210 --> 00:03:24,460