1
00:00:00,000 --> 00:00:03,346
>> [Jouer de la musique]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Très bien.

4
00:00:06,220 --> 00:00:08,140
Donc, la recherche binaire est un
algorithme que nous pouvons utiliser

5
00:00:08,140 --> 00:00:10,530
de trouver un élément à l'intérieur d'un tableau.

6
00:00:10,530 --> 00:00:14,710
Contrairement à la recherche linéaire, il faut une
condition spéciale sera réuni à l'avance,

7
00:00:14,710 --> 00:00:19,020
mais il est tellement plus efficace si
cette condition est, en fait, a rencontré.

8
00:00:19,020 --> 00:00:20,470
>> Alors, quelle est l'idée ici?

9
00:00:20,470 --> 00:00:21,780
il est diviser pour régner.

10
00:00:21,780 --> 00:00:25,100
Nous voulons réduire la taille de
la zone de recherche par moitié chaque fois

11
00:00:25,100 --> 00:00:27,240
afin de trouver un numéro de cible.

12
00:00:27,240 --> 00:00:29,520
Ceci est où cette condition
entre en jeu, cependant.

13
00:00:29,520 --> 00:00:32,740
Nous ne pouvons que tirer parti de la puissance de
l'élimination de la moitié des éléments

14
00:00:32,740 --> 00:00:36,070
sans même regarder
eux si le tableau est trié.

15
00:00:36,070 --> 00:00:39,200
>> Si il est un mélange complet jusqu'à,
Nous ne pouvons pas sortir de la main

16
00:00:39,200 --> 00:00:42,870
jeter la moitié des éléments, parce que
nous ne savons pas ce que nous allons jeter.

17
00:00:42,870 --> 00:00:45,624
Mais si le tableau est trié,
nous pouvons le faire, parce que nous

18
00:00:45,624 --> 00:00:48,040
savoir que tout le
à gauche de l'endroit où nous sommes actuellement

19
00:00:48,040 --> 00:00:50,500
doit être inférieure à la
valeur que nous sommes actuellement à.

20
00:00:50,500 --> 00:00:52,300
Et tout à la
droit de l'endroit où nous sommes

21
00:00:52,300 --> 00:00:55,040
doit être supérieure à la valeur
nous sommes en train de regarder.

22
00:00:55,040 --> 00:00:58,710
>> Alors, quel est le pseudo-
étapes de recherche binaire?

23
00:00:58,710 --> 00:01:02,310
Nous répétons ce processus jusqu'à ce que la
tableau ou, comme nous procédons à travers,

24
00:01:02,310 --> 00:01:07,740
sous-réseaux, des petits morceaux de
le tableau original, est de taille 0.

25
00:01:07,740 --> 00:01:10,960
Calculer le point médian
de la matrice de sous-courant.

26
00:01:10,960 --> 00:01:14,460
>> Si la valeur que vous cherchez est
dans cet élément du tableau, arrêter.

27
00:01:14,460 --> 00:01:15,030
Vous l'avez trouvé.

28
00:01:15,030 --> 00:01:16,550
C'est génial.

29
00:01:16,550 --> 00:01:19,610
Dans le cas contraire, si la cible est
à moins que ce qui est au milieu,

30
00:01:19,610 --> 00:01:23,430
si la valeur que nous recherchons
pour est inférieure à ce que nous voyons,

31
00:01:23,430 --> 00:01:26,780
répéter ce processus, mais
changer le point de fin, à la place

32
00:01:26,780 --> 00:01:29,300
d'être l'original
compléter gamme complète,

33
00:01:29,300 --> 00:01:34,110
à être juste à la gauche
d'où nous venons d'examiner.

34
00:01:34,110 --> 00:01:38,940
>> Nous savions que le milieu était trop élevé,
ou la cible est inférieure à la moyenne,

35
00:01:38,940 --> 00:01:42,210
et il doit exister, si elle
existe à tous les dans le tableau,

36
00:01:42,210 --> 00:01:44,660
quelque part à la gauche du point médian.

37
00:01:44,660 --> 00:01:48,120
Et donc nous allons mettre le tableau
emplacement juste à gauche

38
00:01:48,120 --> 00:01:51,145
du milieu en tant que nouveau point de fin.

39
00:01:51,145 --> 00:01:53,770
A l'inverse, si la cible est
supérieure à ce qui est au milieu,

40
00:01:53,770 --> 00:01:55,750
nous faisons exactement la même
processus, mais à la place nous

41
00:01:55,750 --> 00:01:59,520
changer le point de départ pour être
juste à la droite du point central

42
00:01:59,520 --> 00:02:00,680
nous vient de calculer.

43
00:02:00,680 --> 00:02:03,220
Et puis, on recommence le processus.

44
00:02:03,220 --> 00:02:05,220
>> Disons Visualiser cette, OK?

45
00:02:05,220 --> 00:02:08,620
Donc, il ya beaucoup de choses, et ici,
mais voici un tableau de 15 éléments.

46
00:02:08,620 --> 00:02:11,400
Et nous allons garder la trace
de beaucoup plus de choses cette fois.

47
00:02:11,400 --> 00:02:13,870
Donc, à la recherche linéaire, nous étions
juste se soucier de la cible.

48
00:02:13,870 --> 00:02:15,869
Mais cette fois, nous voulons
soucier où sommes-nous

49
00:02:15,869 --> 00:02:18,480
commencer à chercher, où
nous arrêtons-nous à la recherche,

50
00:02:18,480 --> 00:02:21,876
et ce qui est le point médian
de la gamme actuelle.

51
00:02:21,876 --> 00:02:23,250
Alors on y va avec la recherche binaire.

52
00:02:23,250 --> 00:02:25,290
Nous sommes à peu près bon d'aller, non?

53
00:02:25,290 --> 00:02:28,650
Je vais juste de mettre bas
ci-dessous ici un ensemble d'indices.

54
00:02:28,650 --> 00:02:32,430
Ceci est fondamentalement juste quel élément
du tableau dont nous parlons.

55
00:02:32,430 --> 00:02:34,500
Avec la recherche linéaire, nous
soins, dans la mesure où nous

56
00:02:34,500 --> 00:02:36,800
besoin de savoir combien de
éléments que nous nous parcourons plus,

57
00:02:36,800 --> 00:02:40,010
mais nous ne nous soucions pas vraiment ce
élément que nous sommes en train de regarder.

58
00:02:40,010 --> 00:02:41,014
En recherche binaire, nous le faisons.

59
00:02:41,014 --> 00:02:42,930
Et ce ne sont là
là comme un petit guide.

60
00:02:42,930 --> 00:02:44,910
>> Donc, nous pouvons commencer, non?

61
00:02:44,910 --> 00:02:46,240
Eh bien, pas tout à fait.

62
00:02:46,240 --> 00:02:48,160
Se souvenir de ce que je disais
à propos de la recherche binaire?

63
00:02:48,160 --> 00:02:50,955
Nous ne pouvons pas le faire sur une
tableau non trié ou bien,

64
00:02:50,955 --> 00:02:55,820
nous ne sommes pas garantir que l'
certains éléments ou valeurs ne sont pas

65
00:02:55,820 --> 00:02:57,650
accidentellement
mis au rebut lorsque nous venons

66
00:02:57,650 --> 00:02:59,920
décider d'ignorer la moitié du tableau.

67
00:02:59,920 --> 00:03:02,574
>> Donc, la première étape avec une recherche binaire
est vous devez avoir un tableau trié.

68
00:03:02,574 --> 00:03:05,240
Et vous pouvez utiliser l'un des tri
algorithmes dont nous avons parlé

69
00:03:05,240 --> 00:03:06,700
pour vous rendre à cette position.

70
00:03:06,700 --> 00:03:10,370
Alors maintenant, nous sommes dans une position où
nous pouvons effectuer une recherche binaire.

71
00:03:10,370 --> 00:03:12,560
>> Donc, nous allons répéter le processus
étape par étape et de garder

72
00:03:12,560 --> 00:03:14,830
une trace de ce qui se passe que nous allons.

73
00:03:14,830 --> 00:03:17,980
Donc, le premier que nous devons faire est de calculer
le point médian de la rangée en cours.

74
00:03:17,980 --> 00:03:20,620
Eh bien, nous allons dire que nous sommes d'abord
tous, à la recherche de la valeur 19.

75
00:03:20,620 --> 00:03:22,290
Nous essayons de trouver le numéro 19.

76
00:03:22,290 --> 00:03:25,380
Le premier élément de cette
tableau est situé à l'indice zéro,

77
00:03:25,380 --> 00:03:28,880
et le dernier élément de ce
tableau se trouve à l'index 14.

78
00:03:28,880 --> 00:03:31,430
Et donc nous allons appeler ceux début et de fin.

79
00:03:31,430 --> 00:03:35,387
>> Donc, nous calculons le milieu par
ajoutant 0 plus 14 divisé par 2;

80
00:03:35,387 --> 00:03:36,720
milieu assez simple.

81
00:03:36,720 --> 00:03:40,190
Et nous pouvons dire que
le milieu est maintenant 7.

82
00:03:40,190 --> 00:03:43,370
Donc, est-ce 15 que nous recherchons?

83
00:03:43,370 --> 00:03:43,940
Non ce n'est pas.

84
00:03:43,940 --> 00:03:45,270
Nous recherchons 19.

85
00:03:45,270 --> 00:03:49,400
Mais nous savons que 19 est plus grande
que ce que nous avons trouvé au milieu.

86
00:03:49,400 --> 00:03:52,470
>> Donc, ce que nous pouvons faire est
changer le point de départ

87
00:03:52,470 --> 00:03:57,280
à être juste à droite de la
milieu, et de répéter le processus.

88
00:03:57,280 --> 00:04:01,690
Et quand nous faisons cela, nous disons maintenant
nouveau point de départ est l'emplacement du tableau 8.

89
00:04:01,690 --> 00:04:07,220
Ce que nous avons fait est efficace
tout ignoré à la gauche de 15.

90
00:04:07,220 --> 00:04:09,570
Nous avons éliminé la moitié
du problème, et maintenant,

91
00:04:09,570 --> 00:04:13,510
au lieu d'avoir à chercher
plus de 15 éléments de notre gamme,

92
00:04:13,510 --> 00:04:15,610
nous avons seulement à la recherche de plus de 7.

93
00:04:15,610 --> 00:04:17,706
Donc 8 est le nouveau point de départ.

94
00:04:17,706 --> 00:04:19,600
14 est toujours le point de fin.

95
00:04:19,600 --> 00:04:21,430
>> Et maintenant, nous allons au cours de cette nouveau.

96
00:04:21,430 --> 00:04:22,810
Nous calculons le nouveau milieu.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 est 22, divisé par 2 est 11.

98
00:04:27,130 --> 00:04:28,660
Est-ce ce que nous recherchons?

99
00:04:28,660 --> 00:04:30,110
Non ce n'est pas.

100
00:04:30,110 --> 00:04:32,930
Nous recherchons pour une valeur qui est
moins de ce que nous venons de trouver.

101
00:04:32,930 --> 00:04:34,721
Donc, nous allons répéter
le processus à nouveau.

102
00:04:34,721 --> 00:04:38,280
Nous allons changer le point de fin
être juste à la gauche du point médian.

103
00:04:38,280 --> 00:04:41,800
Ainsi, le nouveau point final devient 10.

104
00:04:41,800 --> 00:04:44,780
Et maintenant, voilà la seule partie de
le tableau que nous avons à trier.

105
00:04:44,780 --> 00:04:48,460
Donc, nous avons maintenant éliminé
12 des 15 éléments.

106
00:04:48,460 --> 00:04:51,550
Nous savons que si 19
existe dans le tableau, il

107
00:04:51,550 --> 00:04:57,210
doit exister quelque part entre l'élément
Numéro 8 et l'élément numéro 10.

108
00:04:57,210 --> 00:04:59,400
>> Donc, nous calculons de nouveau le nouveau milieu.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 est 18, divisé par 2 est 9.

110
00:05:02,900 --> 00:05:05,074
Et dans ce cas, regardez, la
cible se trouve au milieu.

111
00:05:05,074 --> 00:05:06,740
Nous avons trouvé exactement ce que nous recherchons.

112
00:05:06,740 --> 00:05:07,780
Nous pouvons arrêter.

113
00:05:07,780 --> 00:05:10,561
Nous avons terminé avec succès
une recherche binaire.

114
00:05:10,561 --> 00:05:11,060
Bien.

115
00:05:11,060 --> 00:05:13,930
Nous savons donc cet algorithme
fonctionne si la cible est

116
00:05:13,930 --> 00:05:16,070
quelque part à l'intérieur de la matrice.

117
00:05:16,070 --> 00:05:19,060
Est-ce que ce travail de l'algorithme si
la cible se trouve pas dans la matrice?

118
00:05:19,060 --> 00:05:20,810
Eh bien, nous allons commencer ce
à nouveau, et cette fois,

119
00:05:20,810 --> 00:05:23,380
Voyons pour l'élément
16, qui visuellement nous pouvons voir

120
00:05:23,380 --> 00:05:25,620
ne pas exister n'importe où dans le tableau.

121
00:05:25,620 --> 00:05:27,110
>> Le point de départ est à nouveau 0.

122
00:05:27,110 --> 00:05:28,590
Le point final est à nouveau 14.

123
00:05:28,590 --> 00:05:32,490
Ce sont les indices de la première et
derniers éléments de la gamme complète.

124
00:05:32,490 --> 00:05:36,057
Et nous allons passer par le processus que nous venons
a traversé à nouveau, essayer de trouver 16,

125
00:05:36,057 --> 00:05:39,140
même si visuellement, nous pouvons déjà
dire que ça ne va pas être là.

126
00:05:39,140 --> 00:05:43,450
Nous voulons juste vous assurer que cet algorithme
sera, en fait, toujours travailler en quelque sorte

127
00:05:43,450 --> 00:05:46,310
et pas seulement nous laisser
bloqué dans une boucle infinie.

128
00:05:46,310 --> 00:05:48,190
>> Alors, quelle est la première étape?

129
00:05:48,190 --> 00:05:50,230
Calculer le point médian
de la gamme actuelle.

130
00:05:50,230 --> 00:05:52,790
Quel est le point médian
de la gamme actuelle?

131
00:05:52,790 --> 00:05:54,410
Eh bien, il est 7, à droite?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 divisé par 2 est 7.

133
00:05:57,560 --> 00:05:59,280
Est de 15 ce que nous cherchons?

134
00:05:59,280 --> 00:05:59,780
Non.

135
00:05:59,780 --> 00:06:02,930
Il est assez proche, mais nous sommes à la recherche
pour une valeur légèrement plus grand que cela.

136
00:06:02,930 --> 00:06:06,310
>> Donc, nous savons que ça va
être nulle part à la gauche de 15.

137
00:06:06,310 --> 00:06:08,540
La cible est supérieure à
ce qui est dans le milieu.

138
00:06:08,540 --> 00:06:12,450
Et nous avons donc mis le nouveau point de départ pour
être juste à la droite du milieu.

139
00:06:12,450 --> 00:06:16,130
Le point médian est actuellement de 7, de sorte
disons que le nouveau point de départ est de 8.

140
00:06:16,130 --> 00:06:18,130
Et ce que nous avons effectivement
fait nouveau est ignoré

141
00:06:18,130 --> 00:06:21,150
toute la moitié gauche de la matrice.

142
00:06:21,150 --> 00:06:23,750
>> Maintenant, nous répétons le
traiter une fois de plus.

143
00:06:23,750 --> 00:06:24,910
Calculer le nouveau milieu.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 est 22, divisé par 2 est 11.

145
00:06:29,350 --> 00:06:31,060
Est de 23 ce que nous cherchons?

146
00:06:31,060 --> 00:06:31,870
Malheureusement non.

147
00:06:31,870 --> 00:06:34,930
Nous recherchons pour une valeur
qui est inférieur à 23.

148
00:06:34,930 --> 00:06:37,850
Et dans ce cas, nous allons
pour changer le point de fin pour être juste

149
00:06:37,850 --> 00:06:40,035
à la gauche du point médian de courant.

150
00:06:40,035 --> 00:06:43,440
Le point médian actuel est 11, et
donc nous allons définir le nouveau point de fin

151
00:06:43,440 --> 00:06:46,980
pour la prochaine fois que nous allons
à travers ce processus à 10.

152
00:06:46,980 --> 00:06:48,660
>> Encore une fois, nous passons par le processus à nouveau.

153
00:06:48,660 --> 00:06:49,640
Calculer le milieu.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 divisé par 2 est 9.

155
00:06:53,100 --> 00:06:54,750
Est de 19 ce que nous cherchons?

156
00:06:54,750 --> 00:06:55,500
Malheureusement non.

157
00:06:55,500 --> 00:06:58,050
Nous sommes toujours à la recherche de
un nombre inférieur à cela.

158
00:06:58,050 --> 00:07:02,060
Donc, nous allons changer le point de fin pour le moment
à être juste à la gauche du point médian.

159
00:07:02,060 --> 00:07:05,532
Le point médian est actuellement de 9,
de sorte que le point final sera de 8.

160
00:07:05,532 --> 00:07:07,920
Et maintenant, nous cherchons simplement
en un seul ensemble d'éléments.

161
00:07:07,920 --> 00:07:10,250
>> Quel est le point central de ce tableau?

162
00:07:10,250 --> 00:07:13,459
Eh bien, il commence à 8, il
se termine à 8, le point médian est de 8.

163
00:07:13,459 --> 00:07:14,750
Est-ce que ce que nous recherchons?

164
00:07:14,750 --> 00:07:16,339
Cherchons-nous 17?

165
00:07:16,339 --> 00:07:17,380
Non, nous sommes à la recherche 16.

166
00:07:17,380 --> 00:07:20,160
Donc, si elle existe dans la matrice,
il doit exister quelque part

167
00:07:20,160 --> 00:07:21,935
à gauche de l'endroit où nous sommes actuellement.

168
00:07:21,935 --> 00:07:23,060
Alors qu'est-ce qu'on va faire?

169
00:07:23,060 --> 00:07:26,610
Eh bien, nous allons mettre le point final d'être juste
à la gauche du point médian de courant.

170
00:07:26,610 --> 00:07:29,055
Donc, nous allons changer le point de fin à 7.

171
00:07:29,055 --> 00:07:32,120
Voyez-vous ce qui vient
arrivé ici, bien?

172
00:07:32,120 --> 00:07:33,370
Consulter ici maintenant.

173
00:07:33,370 --> 00:07:35,970
>> Démarrer est maintenant supérieure à la fin.

174
00:07:35,970 --> 00:07:39,620
En effet, les deux extrémités
de notre gamme ont traversé,

175
00:07:39,620 --> 00:07:42,252
et le point de départ est
maintenant, après le point de fin.

176
00:07:42,252 --> 00:07:43,960
Eh bien, cela ne veut pas
aucun sens, non?

177
00:07:43,960 --> 00:07:47,960
Alors maintenant, ce que nous pouvons dire est que nous
une matrice de taille sub 0.

178
00:07:47,960 --> 00:07:50,110
Et une fois que nous appris à nous
ce point, nous pouvons maintenant

179
00:07:50,110 --> 00:07:53,940
garantir que l'élément 16
ne pas exister dans la matrice,

180
00:07:53,940 --> 00:07:56,280
parce que le point de départ
et le point final ont traversé.

181
00:07:56,280 --> 00:07:58,340
Et il est donc pas là.

182
00:07:58,340 --> 00:08:01,340
Maintenant, notez que ce qui est légèrement
différent du point de début et de fin

183
00:08:01,340 --> 00:08:02,900
point étant le même.

184
00:08:02,900 --> 00:08:05,030
Si nous avions été à la recherche
pour 17, il aurait

185
00:08:05,030 --> 00:08:08,870
été dans le tableau, et le point de départ
et le point de cette dernière itération de fin

186
00:08:08,870 --> 00:08:11,820
avant ces points croisés,
nous aurions trouvé 17 là.

187
00:08:11,820 --> 00:08:15,510
Il est seulement quand ils se croisent que nous pouvons
garantir que l'élément ne fonctionne pas

188
00:08:15,510 --> 00:08:17,180
exister dans le tableau.

189
00:08:17,180 --> 00:08:20,260
>> Prenons donc beaucoup moins
étapes que la recherche linéaire.

190
00:08:20,260 --> 00:08:23,250
Dans le pire des cas, nous avons eu
de diviser une liste de n éléments

191
00:08:23,250 --> 00:08:27,770
à plusieurs reprises dans la moitié pour trouver la cible,
soit parce que l'élément de cible

192
00:08:27,770 --> 00:08:33,110
sera quelque part dans la dernière
division, ou il ne existe pas du tout.

193
00:08:33,110 --> 00:08:37,830
Ainsi, dans le pire des cas, nous devons
diviser les array-- savez-vous?

194
00:08:37,830 --> 00:08:40,510
Connexion de n fois; nous
avoir à couper le problème

195
00:08:40,510 --> 00:08:42,610
dans une moitié certain nombre de fois.

196
00:08:42,610 --> 00:08:45,160
Ce nombre de fois est log n.

197
00:08:45,160 --> 00:08:46,510
>> Quel est le meilleur scénario?

198
00:08:46,510 --> 00:08:48,899
Eh bien, la première nous de temps
calculer le milieu,

199
00:08:48,899 --> 00:08:50,190
nous trouvons ce que nous cherchons.

200
00:08:50,190 --> 00:08:52,150
Dans tous les précédents
exemples sur la recherche binaire

201
00:08:52,150 --> 00:08:55,489
nous venons tout juste dépassé, si nous avions
été à la recherche de l'élément 15,

202
00:08:55,489 --> 00:08:57,030
nous aurions trouvé immédiatement.

203
00:08:57,030 --> 00:08:58,321
Ce fut dès le début.

204
00:08:58,321 --> 00:09:01,200
Ce fut le point médian de
la première tentative d'une scission

205
00:09:01,200 --> 00:09:03,950
d'une division à la recherche binaire.

206
00:09:03,950 --> 00:09:06,350
>> Et si dans le pire
cas, la recherche binaire fonctionne

207
00:09:06,350 --> 00:09:11,580
dans le journal n, ce qui est nettement mieux
de la recherche linéaire, dans le pire des cas.

208
00:09:11,580 --> 00:09:16,210
Dans le meilleur des cas, binaire
recherche fonctionne en oméga de 1.

209
00:09:16,210 --> 00:09:18,990
Donc, la recherche binaire est beaucoup
mieux que la recherche linéaire,

210
00:09:18,990 --> 00:09:23,270
mais vous avez à traiter avec le processus de
le tri d'abord votre réseau avant de pouvoir

211
00:09:23,270 --> 00:09:26,140
tirer parti de la puissance de la recherche binaire.

212
00:09:26,140 --> 00:09:27,130
>> Je suis Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Ceci est 50 CS.

214
00:09:29,470 --> 00:09:31,070