1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Salut, je suis Rob.

3
00:00:15,010 --> 00:00:16,790
Comment nous employons faire une recherche binaire?

4
00:00:16,790 --> 00:00:18,770
Voyons.

5
00:00:18,770 --> 00:00:23,400
Donc, notez que cette recherche nous allons
à mettre en oeuvre de manière récursive.

6
00:00:23,400 --> 00:00:27,470
Vous pouvez également mettre en œuvre une recherche binaire
itérative, donc si vous l'avez fait,

7
00:00:27,470 --> 00:00:29,280
c'est tout à fait correct.

8
00:00:29,280 --> 00:00:32,820
>> Maintenant abord, rappelons ce que le
paramètres de recherche sont censés être.

9
00:00:32,820 --> 00:00:36,120
Ici, nous voyons la valeur int, ce qui est
censé être la valeur que l'utilisateur est

10
00:00:36,120 --> 00:00:37,320
chercher.

11
00:00:37,320 --> 00:00:40,800
Nous voyons les valeurs int tableau, ce qui
est la matrice dans laquelle nous sommes

12
00:00:40,800 --> 00:00:42,520
la recherche de valeur.

13
00:00:42,520 --> 00:00:45,602
Et nous voyons int n, qui est
la longueur de notre réseau.

14
00:00:45,602 --> 00:00:47,410
>> Maintenant, la première chose que le premier.

15
00:00:47,410 --> 00:00:51,350
Nous vérifions pour voir si n est égal à 0, dans
auquel cas l'on retourne faux.

16
00:00:51,350 --> 00:00:54,770
C'est tout simplement dire que si nous avons un vide
array, value n'est clairement pas dans un

17
00:00:54,770 --> 00:00:57,860
tableau vide, afin que nous puissions retourner false.

18
00:00:57,860 --> 00:01:01,250
>> Maintenant, nous voulons vraiment faire le binaire
Recherche partie de la recherche binaire.

19
00:01:01,250 --> 00:01:04,780
Donc, nous voulons trouver le milieu
élément de ce tableau.

20
00:01:04,780 --> 00:01:09,130
Ici, nous disons milieu égale n divisé
par deux, étant donné que l'élément intermédiaire est

21
00:01:09,130 --> 00:01:12,240
va être la longueur d'
notre tableau divisé par 2.

22
00:01:12,240 --> 00:01:15,040
Maintenant, nous allons vérifier pour voir si le
élément central est égale à la valeur que nous sommes

23
00:01:15,040 --> 00:01:16,160
chercher.

24
00:01:16,160 --> 00:01:21,030
Donc, si les valeurs moyenne égale valeur, nous
peut retourner vrai que nous avons trouvé l'

25
00:01:21,030 --> 00:01:22,810
valeur dans notre tableau.

26
00:01:22,810 --> 00:01:26,380
>> Mais si ce n'était pas vrai, maintenant
nous devons faire la récursif

27
00:01:26,380 --> 00:01:27,840
étape de recherche binaire.

28
00:01:27,840 --> 00:01:30,450
Nous devons chercher soit à l'
à gauche de la matrice ou à l'

29
00:01:30,450 --> 00:01:32,320
milieu de la rangée.

30
00:01:32,320 --> 00:01:39,280
Donc, ici, nous disons si les valeurs de milieu est
moins de valeur, ce qui signifie que la valeur

31
00:01:39,280 --> 00:01:41,350
est supérieure à la moyenne
de la matrice.

32
00:01:41,350 --> 00:01:45,790
Donc, la valeur doit être à droite de la
élément que nous venons d'examiner.

33
00:01:45,790 --> 00:01:48,090
>> Donc, ici, nous allons
rechercher de manière récursive.

34
00:01:48,090 --> 00:01:50,320
Et nous allons voir ce que nous passons
pour cela d'une seconde.

35
00:01:50,320 --> 00:01:53,440
Mais nous allons chercher à l'
droit de l'élément intermédiaire.

36
00:01:53,440 --> 00:01:57,710
Et dans l'autre cas, cela signifie que
la valeur était inférieure à la moyenne de l'

37
00:01:57,710 --> 00:02:00,660
tableau, et ainsi nous allons
à la recherche à la gauche.

38
00:02:00,660 --> 00:02:03,520
Maintenant, la gauche va être
un peu plus facile à regarder.

39
00:02:03,520 --> 00:02:07,770
Ainsi, nous voyons ici que nous sommes de façon récursive
appelant la recherche où la première

40
00:02:07,770 --> 00:02:10,120
argument est, à nouveau, la valeur
nous sommes à la recherche sur.

41
00:02:10,120 --> 00:02:14,970
Le deuxième argument est va être la
tableau que nous cherchions sur.

42
00:02:14,970 --> 00:02:17,090
Et le dernier élément est maintenant milieu.

43
00:02:17,090 --> 00:02:21,650
Rappelez-vous le dernier paramètre est notre int
n, de sorte que c'est la longueur de notre réseau.

44
00:02:21,650 --> 00:02:25,310
>> Dans l'appel récursif à la recherche, nous sommes
maintenant dire que la longueur de l'

45
00:02:25,310 --> 00:02:27,230
tableau est moyenne.

46
00:02:27,230 --> 00:02:32,900
Donc, si notre tableau était d'une taille 20 et nous
recherché à l'indice 10, depuis la mi-est

47
00:02:32,900 --> 00:02:36,930
20 divisé par 2, cela signifie que nous sommes
passant de 10 en tant que nouveau

48
00:02:36,930 --> 00:02:38,300
longueur de notre réseau.

49
00:02:38,300 --> 00:02:41,910
N'oubliez pas que lorsque vous avez un tableau
longueur de 10, cela signifie que la validité

50
00:02:41,910 --> 00:02:45,450
les éléments sont des indices de 0 à 9.

51
00:02:45,450 --> 00:02:50,120
Donc, c'est exactement ce que nous voulons
indiquer notre tableau mis à jour - la gauche

52
00:02:50,120 --> 00:02:53,010
tableau à partir de l'élément intermédiaire.

53
00:02:53,010 --> 00:02:55,710
>> Ainsi, en regardant vers la droite est
un peu plus difficile.

54
00:02:55,710 --> 00:03:00,170
Maintenant abord, nous allons examiner la longueur
de la matrice vers la droite de l'

55
00:03:00,170 --> 00:03:01,240
élément central.

56
00:03:01,240 --> 00:03:08,390
Donc, si notre tableau était de taille n, alors la
nouveau tableau sera de taille n moins

57
00:03:08,390 --> 00:03:10,140
moins milieu 1.

58
00:03:10,140 --> 00:03:12,530
Donc, nous allons penser à n moins moyenne.

59
00:03:12,530 --> 00:03:18,710
>> Encore une fois, si le tableau était de la taille 20 et
nous divisons par 2 pour obtenir la moyenne,

60
00:03:18,710 --> 00:03:23,540
de sorte que le milieu est 10, n moins milieu
va nous donner 10, donc 10

61
00:03:23,540 --> 00:03:25,330
éléments à droite du milieu.

62
00:03:25,330 --> 00:03:27,780
Mais nous avons aussi ce moins
1, puisque nous ne voulons pas

63
00:03:27,780 --> 00:03:29,700
inclure le milieu lui-même.

64
00:03:29,700 --> 00:03:34,190
Alors n moins milieu moins 1 nous donne la
nombre total d'éléments vers la droite

65
00:03:34,190 --> 00:03:36,800
de l'indice du milieu dans le tableau.

66
00:03:36,800 --> 00:03:41,870
>> Maintenant ici, n'oubliez pas que le milieu
paramètre est le tableau des valeurs.

67
00:03:41,870 --> 00:03:46,180
Donc, ici, nous passons une
mise à jour des valeurs tableau.

68
00:03:46,180 --> 00:03:50,930
Ces valeurs plus plus milieu 1 est
fait dire appeler de façon récursive

69
00:03:50,930 --> 00:03:56,460
recherche, en passant dans un nouveau tableau, où
cette nouvelle gamme commence au milieu

70
00:03:56,460 --> 00:03:59,370
plus une origine de notre tableau de valeurs.

71
00:03:59,370 --> 00:04:05,400
>> Une syntaxe alternative pour que, maintenant que
vous avez commencé à voir des pointeurs, est

72
00:04:05,400 --> 00:04:10,170
valeurs esperluette, plus milieu 1.

73
00:04:10,170 --> 00:04:17,149
Alors, prenez l'adresse du milieu
plus un élément de valeurs.

74
00:04:17,149 --> 00:04:23,690
>> Maintenant, si vous n'étiez pas à l'aise
modification d'un tableau comme ça, vous

75
00:04:23,690 --> 00:04:28,900
pourrait également avoir mis en œuvre cette aide
une fonction d'assistance récursive, où

76
00:04:28,900 --> 00:04:31,680
que fonction d'assistance prend
plusieurs arguments.

77
00:04:31,680 --> 00:04:36,610
Ainsi, au lieu de prendre simplement la valeur, la
matrice, et la taille de la matrice,

78
00:04:36,610 --> 00:04:42,315
la fonction d'assistance pourrait prendre plus
arguments, y compris l'indice inférieur

79
00:04:42,315 --> 00:04:45,280
que vous vous souciez de la matrice
et l'indice supérieur que vous vous souciez

80
00:04:45,280 --> 00:04:46,300
sur le tableau.

81
00:04:46,300 --> 00:04:49,770
>> Et ainsi garder la trace de deux bas
indice et l'indice supérieure, vous ne

82
00:04:49,770 --> 00:04:52,780
doivent jamais modifier le
valeurs initiales tableau.

83
00:04:52,780 --> 00:04:56,390
Vous pouvez tout simplement continuer à
utiliser le tableau de valeurs.

84
00:04:56,390 --> 00:04:59,540
Mais ici, remarquons que nous n'avons pas besoin d'une aide
fonctionner aussi longtemps que nous sommes

85
00:04:59,540 --> 00:05:01,760
prêt à modifier l'original
valeurs tableau.

86
00:05:01,760 --> 00:05:05,020
Nous sommes prêts à passer à
un valeurs mises à jour.

87
00:05:05,020 --> 00:05:09,140
>> Maintenant, nous ne pouvons pas la recherche binaire sur
un tableau non trié.

88
00:05:09,140 --> 00:05:12,220
Donc, nous allons obtenir ce triés.

89
00:05:12,220 --> 00:05:17,650
Maintenant, remarquez ce genre est passé de deux
int valeurs des paramètres, qui est le

90
00:05:17,650 --> 00:05:21,110
tableau que nous le tri, et int n,
qui est la longueur du réseau que

91
00:05:21,110 --> 00:05:22,250
nous le tri.

92
00:05:22,250 --> 00:05:24,840
Donc, ici, nous voulons mettre en œuvre
un algorithme de tri

93
00:05:24,840 --> 00:05:26,690
c'est o n carré.

94
00:05:26,690 --> 00:05:30,560
Vous pouvez choisir bulle tri, la sélection
tri ou le tri par insertion, ou

95
00:05:30,560 --> 00:05:32,670
une autre sorte que nous n'avons pas
vu en classe.

96
00:05:32,670 --> 00:05:36,380
Mais ici, nous allons
utiliser la sélection sorte.

97
00:05:36,380 --> 00:05:40,030
>> Donc, nous allons parcourir
sur l'ensemble du réseau.

98
00:05:40,030 --> 00:05:44,360
Eh bien, ici nous voyons que nous sommes itération
de 0 à n moins 1.

99
00:05:44,360 --> 00:05:45,990
Pourquoi ne pas tout le chemin jusqu'à n?

100
00:05:45,990 --> 00:05:49,320
Eh bien, si nous avons déjà trié la première
n moins 1 éléments, puis le

101
00:05:49,320 --> 00:05:54,420
dernier élément qui doit déjà être
au bon endroit, si le tri sur

102
00:05:54,420 --> 00:05:56,520
l'ensemble du réseau.

103
00:05:56,520 --> 00:05:58,770
>> Maintenant, rappelez-vous comment la sélection
travaux de tri.

104
00:05:58,770 --> 00:06:01,950
Nous allons passer en revue l'ensemble du réseau
la recherche de la valeur minimum dans

105
00:06:01,950 --> 00:06:04,480
la matrice et le bâton que
au début.

106
00:06:04,480 --> 00:06:07,610
Ensuite, nous allons passer en revue l'ensemble du
tableau à nouveau à la recherche de la deuxième

107
00:06:07,610 --> 00:06:10,410
plus petit élément, et le bâton que
dans la deuxième position dans la

108
00:06:10,410 --> 00:06:12,100
tableau, et ainsi de suite.

109
00:06:12,100 --> 00:06:14,330
Donc, c'est ce que ce fait.

110
00:06:14,330 --> 00:06:17,290
>> Ici, nous voyons que nous sommes
réglage du minimum actuel

111
00:06:17,290 --> 00:06:20,030
La valeur de l'indice i-ième.

112
00:06:20,030 --> 00:06:23,160
Ainsi, sur la première itération, nous allons
de considérer la valeur minimum pour être

113
00:06:23,160 --> 00:06:25,030
le début de notre tableau.

114
00:06:25,030 --> 00:06:28,500
Ensuite, nous allons parcourir la
reste de la matrice, en contrôlant

115
00:06:28,500 --> 00:06:31,870
voir s'il ya des éléments plus petits que
celle que nous sommes actuellement

116
00:06:31,870 --> 00:06:33,900
compte tenu du minimum.

117
00:06:33,900 --> 00:06:38,840
>> Donc, ici, les valeurs j plus un - c'est
moins que ce que nous sommes actuellement

118
00:06:38,840 --> 00:06:40,380
compte tenu du minimum.

119
00:06:40,380 --> 00:06:42,940
Ensuite, nous allons mettre à jour ce
nous pensons que c'est le minimum à

120
00:06:42,940 --> 00:06:44,640
indice j + 1.

121
00:06:44,640 --> 00:06:48,540
Alors, le faire à travers l'ensemble du réseau,
et après cette boucle, minimum

122
00:06:48,540 --> 00:06:53,160
doit être au minimum de l'élément
la position de la i-ème dans le tableau.

123
00:06:53,160 --> 00:06:57,350
>> Une fois que nous avons, nous pouvons échanger l'
valeur minimale dans la position i-ième

124
00:06:57,350 --> 00:06:58,230
dans le tableau.

125
00:06:58,230 --> 00:07:00,130
Donc, c'est juste un échange standard.

126
00:07:00,130 --> 00:07:03,940
Nous conservons une valeur temporaire -
la valeur de la i-ème dans le tableau -

127
00:07:03,940 --> 00:07:08,460
la mise en valeur de la i-ème dans le tableau de la
valeur minimale qui appartient là,

128
00:07:08,460 --> 00:07:13,580
puis stocker en retour d'où la
valeur minimale de courant utilisé pour la

129
00:07:13,580 --> 00:07:16,460
i-ième valeur dans le tableau, de sorte que
que nous n'avons pas le perdre.

130
00:07:16,460 --> 00:07:20,510
>> Alors, qui continue sur
l'itération suivante.

131
00:07:20,510 --> 00:07:23,480
Nous allons commencer la recherche de la deuxième
valeur minimale et l'insérer dans le

132
00:07:23,480 --> 00:07:24,590
seconde position.

133
00:07:24,590 --> 00:07:27,440
Sur la troisième itération, nous chercherons
la valeur minimale et la troisième pièce rapportée

134
00:07:27,440 --> 00:07:31,550
que dans la troisième position, et ainsi
jusqu'à ce que nous avons un tableau trié.

135
00:07:31,550 --> 00:07:33,820
Mon nom est Rob, et ce
était la sélection sorte.

136
00:07:33,820 --> 00:07:39,456