1
00:00:00,000 --> 00:00:03,346
>> [REPRODUCCIÓ DE MÚSICA]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: D'acord.

4
00:00:06,220 --> 00:00:08,140
Així que la recerca binària és un
algoritme podem utilitzar

5
00:00:08,140 --> 00:00:10,530
per trobar un element dins d'una matriu.

6
00:00:10,530 --> 00:00:14,710
A diferència de recerca lineal, es requereix un
condició especial es va reunir amb anterioritat,

7
00:00:14,710 --> 00:00:19,020
però és molt més eficient si
aquesta condició és, de fet, s'ha reunit.

8
00:00:19,020 --> 00:00:20,470
>> Quina és la idea aquí?

9
00:00:20,470 --> 00:00:21,780
és divideix i venceràs.

10
00:00:21,780 --> 00:00:25,100
Volem reduir la mida de
l'àrea de recerca a la meitat cada vegada

11
00:00:25,100 --> 00:00:27,240
amb la finalitat de trobar un número de destinació.

12
00:00:27,240 --> 00:00:29,520
Aquí és on aquesta condició
entra en joc, però.

13
00:00:29,520 --> 00:00:32,740
Només podem aprofitar el poder de
eliminant mitjà dels elements

14
00:00:32,740 --> 00:00:36,070
sense tan sols mirar
si la matriu s'ordenen.

15
00:00:36,070 --> 00:00:39,200
>> Si es tracta d'una barreja completa fins,
No podem sortir de la mà

16
00:00:39,200 --> 00:00:42,870
descartar mitjà dels elements, perquè
no sabem el que estem rebutjant.

17
00:00:42,870 --> 00:00:45,624
Però si la matriu està ordenada,
podem fer això, perquè nosaltres

18
00:00:45,624 --> 00:00:48,040
saber que tot a la
esquerre d'on actualment estem

19
00:00:48,040 --> 00:00:50,500
ha de ser inferior a la
valor que estem actualment.

20
00:00:50,500 --> 00:00:52,300
I tot a la
dreta d'on estem

21
00:00:52,300 --> 00:00:55,040
ha de ser més gran que el valor
actualment estem veient.

22
00:00:55,040 --> 00:00:58,710
>> Quin és el pseudocodi
passos per a la recerca binària?

23
00:00:58,710 --> 00:01:02,310
Repetim aquest procés fins que el
matriu o, a mesura que avancem a través,

24
00:01:02,310 --> 00:01:07,740
matrius sub, petites peces de
la matriu original, és de mida 0.

25
00:01:07,740 --> 00:01:10,960
Calcular el punt mitjà
de la matriu sub actual.

26
00:01:10,960 --> 00:01:14,460
>> Si el valor que estàs buscant és
en aquest element de la matriu, per.

27
00:01:14,460 --> 00:01:15,030
Vostè va trobar.

28
00:01:15,030 --> 00:01:16,550
Això és genial.

29
00:01:16,550 --> 00:01:19,610
Altrament, si l'objectiu és
menys del que està al mig,

30
00:01:19,610 --> 00:01:23,430
pel que si el valor que estem buscant
per és menor que el que veiem,

31
00:01:23,430 --> 00:01:26,780
repetir aquest procés una altra vegada, però
canviar el punt final, en comptes

32
00:01:26,780 --> 00:01:29,300
de ser l'original
completar arsenal complet,

33
00:01:29,300 --> 00:01:34,110
per ser just a l'esquerra
d'on ens mirem.

34
00:01:34,110 --> 00:01:38,940
>> Sabíem que el mitjà era massa alt,
o l'objectiu era menys de la meitat,

35
00:01:38,940 --> 00:01:42,210
i pel que ha d'existir, si
existeix en absolut en l'array,

36
00:01:42,210 --> 00:01:44,660
en algun lloc a l'esquerra del punt mitjà.

37
00:01:44,660 --> 00:01:48,120
I així anem a establir la matriu
ubicació just a l'esquerra

38
00:01:48,120 --> 00:01:51,145
del punt mig com el nou punt final.

39
00:01:51,145 --> 00:01:53,770
Al revés, si l'objectiu és
més gran que el que està en el mig,

40
00:01:53,770 --> 00:01:55,750
fem el mateix exacta
procés, però en lloc d'això

41
00:01:55,750 --> 00:01:59,520
canviar el punt d'inici per a ser
just a la dreta del punt mig

42
00:01:59,520 --> 00:02:00,680
simplement calculem.

43
00:02:00,680 --> 00:02:03,220
I llavors, vam començar el procés de nou.

44
00:02:03,220 --> 00:02:05,220
>> Anem a visualitzar això, d'acord?

45
00:02:05,220 --> 00:02:08,620
Així que hi ha molt a fer i aquí,
però aquí és una matriu dels 15 elements.

46
00:02:08,620 --> 00:02:11,400
I farem el seguiment
de moltes més coses en aquesta ocasió.

47
00:02:11,400 --> 00:02:13,870
Així que en recerca lineal, estàvem
simplement preocupar-se per un objectiu.

48
00:02:13,870 --> 00:02:15,869
Però aquesta vegada volem
preocupar-se per on som

49
00:02:15,869 --> 00:02:18,480
començant a mirar, on
ens aturem a la recerca,

50
00:02:18,480 --> 00:02:21,876
i el que és el punt mig
de la matriu actual.

51
00:02:21,876 --> 00:02:23,250
Així que aquí anem amb recerca binària.

52
00:02:23,250 --> 00:02:25,290
Estem bastant bo per anar, oi?

53
00:02:25,290 --> 00:02:28,650
Jo només vaig a posar baix
a continuació aquí un conjunt d'índexs.

54
00:02:28,650 --> 00:02:32,430
Això és bàsicament el que l'element
de la matriu que estem parlant.

55
00:02:32,430 --> 00:02:34,500
Amb la recerca lineal, es
cura, ja que ens

56
00:02:34,500 --> 00:02:36,800
necessita saber quants
elements que estem interactuant sobre,

57
00:02:36,800 --> 00:02:40,010
però en realitat no importa el que
element que actualment estem veient.

58
00:02:40,010 --> 00:02:41,014
En recerca binària, el que fem.

59
00:02:41,014 --> 00:02:42,930
I així, aquests són només
allà com una petita guia.

60
00:02:42,930 --> 00:02:44,910
>> Així que podem començar, no?

61
00:02:44,910 --> 00:02:46,240
Bé, no del tot.

62
00:02:46,240 --> 00:02:48,160
Recordeu el que vaig dir
sobre recerca binària?

63
00:02:48,160 --> 00:02:50,955
No podem fer-ho en una
array sense ordenar o en cas contrari,

64
00:02:50,955 --> 00:02:55,820
no estem garantint que el
certs elements o valors no són

65
00:02:55,820 --> 00:02:57,650
sent accidentalment
rebutjat quan només

66
00:02:57,650 --> 00:02:59,920
decidir ignorar mitjà de la matriu.

67
00:02:59,920 --> 00:03:02,574
>> Així que passo una amb recerca binària
és que ha de tenir un conjunt ordenat.

68
00:03:02,574 --> 00:03:05,240
I vostè pot utilitzar qualsevol de la classificació
algoritmes que hem parlat

69
00:03:05,240 --> 00:03:06,700
per arribar a aquesta posició.

70
00:03:06,700 --> 00:03:10,370
Així que ara, estem en una posició en la
podem fer la cerca binària.

71
00:03:10,370 --> 00:03:12,560
>> Així que repetirem el procés
pas a pas i tenir

72
00:03:12,560 --> 00:03:14,830
la pista del que està succeint a mesura que avancem.

73
00:03:14,830 --> 00:03:17,980
Així que el primer que cal fer és calcular
el punt mig de la matriu actual.

74
00:03:17,980 --> 00:03:20,620
Bé, anem a dir que som, en primer
tot, buscant el valor 19.

75
00:03:20,620 --> 00:03:22,290
Estem tractant de trobar el número 19.

76
00:03:22,290 --> 00:03:25,380
El primer element d'aquesta
matriu es troba en l'índex zero,

77
00:03:25,380 --> 00:03:28,880
i l'últim element d'aquesta
matriu es troba en l'índex 14.

78
00:03:28,880 --> 00:03:31,430
I així anem a cridar els d'inici i fi.

79
00:03:31,430 --> 00:03:35,387
>> Així es calcula el punt mitjà per
l'addició de 0, més 14 dividit per 2;

80
00:03:35,387 --> 00:03:36,720
punt mitjà bastant senzill.

81
00:03:36,720 --> 00:03:40,190
I podem dir que
el punt mitjà és ara 7.

82
00:03:40,190 --> 00:03:43,370
Així que és 15 el que estem buscant?

83
00:03:43,370 --> 00:03:43,940
No, no ho és.

84
00:03:43,940 --> 00:03:45,270
Estem buscant a 19.

85
00:03:45,270 --> 00:03:49,400
Però sabem que 19 és més gran
del que trobem al centre.

86
00:03:49,400 --> 00:03:52,470
>> Així que el que podem fer és
canviar el punt d'inici

87
00:03:52,470 --> 00:03:57,280
per ser just a la dreta de la
punt mig, i repetir el procés de nou.

88
00:03:57,280 --> 00:04:01,690
I quan ho fem, diem ara la
nou punt de partida és la ubicació matriu agost.

89
00:04:01,690 --> 00:04:07,220
El que hem fet és efectiva
tot el ignorat a l'esquerra 15.

90
00:04:07,220 --> 00:04:09,570
Hem eliminat mitjana
del problema, i ara,

91
00:04:09,570 --> 00:04:13,510
en lloc d'haver de buscar
més de 15 elements en la nostra sèrie,

92
00:04:13,510 --> 00:04:15,610
només hem de buscar més de 7.

93
00:04:15,610 --> 00:04:17,706
Així que 8 és el nou punt d'inici.

94
00:04:17,706 --> 00:04:19,600
14 segueix sent el punt final.

95
00:04:19,600 --> 00:04:21,430
>> I ara, anem sobre això de nou.

96
00:04:21,430 --> 00:04:22,810
Calculem el nou punt mitjà.

97
00:04:22,810 --> 00:04:27,130
8 més 14 és 22, dividit per 2 és 11.

98
00:04:27,130 --> 00:04:28,660
És això el que estem buscant?

99
00:04:28,660 --> 00:04:30,110
No, no ho és.

100
00:04:30,110 --> 00:04:32,930
Estem buscant a un valor que és
menys del que acabem de trobar.

101
00:04:32,930 --> 00:04:34,721
Així que repetirem
el procés de nou.

102
00:04:34,721 --> 00:04:38,280
Anem a canviar el punt final a
ser just a l'esquerra del punt mitjà.

103
00:04:38,280 --> 00:04:41,800
Així que el nou punt final es converteix en 10.

104
00:04:41,800 --> 00:04:44,780
I ara, aquesta és l'única part de
la matriu que hem de classificar.

105
00:04:44,780 --> 00:04:48,460
Així que ara hem eliminat
12 dels 15 elements.

106
00:04:48,460 --> 00:04:51,550
Sabem que si 19
existeix en la matriu,

107
00:04:51,550 --> 00:04:57,210
ha d'existir en algun lloc entre l'element
número 8 i l'element número 10.

108
00:04:57,210 --> 00:04:59,400
>> Així es calcula el nou punt mitjà nou.

109
00:04:59,400 --> 00:05:02,900
8 més 10 és 18, dividit per 2 és 9.

110
00:05:02,900 --> 00:05:05,074
I en aquest cas, mira, la
objectiu està al centre.

111
00:05:05,074 --> 00:05:06,740
Ens trobem exactament el que estem buscant.

112
00:05:06,740 --> 00:05:07,780
Podem parar.

113
00:05:07,780 --> 00:05:10,561
Hem completat amb èxit
una recerca binària.

114
00:05:10,561 --> 00:05:11,060
Tot bé.

115
00:05:11,060 --> 00:05:13,930
Així que sabem que aquest algoritme
funciona si l'objectiu és

116
00:05:13,930 --> 00:05:16,070
en algun lloc dins de la matriu.

117
00:05:16,070 --> 00:05:19,060
Funciona això algoritme si
l'objectiu no està en la matriu?

118
00:05:19,060 --> 00:05:20,810
Bé, anem a començar que
de nou, i aquesta vegada,

119
00:05:20,810 --> 00:05:23,380
anem a veure per l'element
16, que visualment es pot veure

120
00:05:23,380 --> 00:05:25,620
no existeix en qualsevol part de la matriu.

121
00:05:25,620 --> 00:05:27,110
>> El punt d'inici és de nou 0.

122
00:05:27,110 --> 00:05:28,590
El punt final és de nou 14.

123
00:05:28,590 --> 00:05:32,490
Aquests són els índexs de la primera i
últims elements de la matriu completa.

124
00:05:32,490 --> 00:05:36,057
I anem a anar a través del procés que acabem de
va ser a través de nou, tractant de trobar 16,

125
00:05:36,057 --> 00:05:39,140
tot i que visualment, ja podem
diuen que no va a ser-hi.

126
00:05:39,140 --> 00:05:43,450
Només volem assegurar-nos que aquest algorisme
serà, de fet, segueixen treballant d'alguna manera

127
00:05:43,450 --> 00:05:46,310
i no només ens deixen
atrapat en un bucle infinit.

128
00:05:46,310 --> 00:05:48,190
>> Quin és el primer pas?

129
00:05:48,190 --> 00:05:50,230
Calcular el punt mitjà
de la matriu actual.

130
00:05:50,230 --> 00:05:52,790
Quin és el punt mig
de la matriu actual?

131
00:05:52,790 --> 00:05:54,410
Bé, és 7, no?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 dividit per 2 és 7.

133
00:05:57,560 --> 00:05:59,280
És de 15 que estem buscant?

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

135
00:05:59,780 --> 00:06:02,930
Està bastant a prop, però estem buscant
per un valor una mica més gran que això.

136
00:06:02,930 --> 00:06:06,310
>> Així que sabem que es va a
estar enlloc a l'esquerra 15.

137
00:06:06,310 --> 00:06:08,540
L'objectiu és més gran que
el que està en el punt mig.

138
00:06:08,540 --> 00:06:12,450
I així ens vam posar en el nou punt de partida per a
ser just a la dreta del centre.

139
00:06:12,450 --> 00:06:16,130
El punt mitjà és actualment 7, de manera que
diguem que el nou punt d'inici és 8.

140
00:06:16,130 --> 00:06:18,130
I el que hem efectivament
fet nou és ignorat

141
00:06:18,130 --> 00:06:21,150
tota la meitat esquerra de la matriu.

142
00:06:21,150 --> 00:06:23,750
>> Ara, repetim el
processar una vegada més.

143
00:06:23,750 --> 00:06:24,910
Calcular el nou punt mitjà.

144
00:06:24,910 --> 00:06:29,350
8 més 14 és 22, dividit per 2 és 11.

145
00:06:29,350 --> 00:06:31,060
És de 23 que estem buscant?

146
00:06:31,060 --> 00:06:31,870
Lamentablement no.

147
00:06:31,870 --> 00:06:34,930
Estem buscant a un valor
que és menor que 23.

148
00:06:34,930 --> 00:06:37,850
I així, en aquest cas, anem
per canviar el punt final per ser just

149
00:06:37,850 --> 00:06:40,035
a l'esquerra del punt mitjà actual.

150
00:06:40,035 --> 00:06:43,440
El punt mitjà actual és 11, i
així que anem a establir el nou punt final

151
00:06:43,440 --> 00:06:46,980
per a la propera vegada que anem
a través d'aquest procés a 10.

152
00:06:46,980 --> 00:06:48,660
>> Un cop més, vam passar pel procés de nou.

153
00:06:48,660 --> 00:06:49,640
Calcular el punt mitjà.

154
00:06:49,640 --> 00:06:53,100
8 més de 10 dividit per 2 és 9.

155
00:06:53,100 --> 00:06:54,750
És de 19 que estem buscant?

156
00:06:54,750 --> 00:06:55,500
Lamentablement no.

157
00:06:55,500 --> 00:06:58,050
Encara estem buscant
un nombre menor que això.

158
00:06:58,050 --> 00:07:02,060
Així que anem a canviar el punt final d'aquest temps
per ser just a l'esquerra del punt mitjà.

159
00:07:02,060 --> 00:07:05,532
El punt mitjà és actualment 9,
de manera que el punt final serà de 8.

160
00:07:05,532 --> 00:07:07,920
I ara, només estem buscant
en un sol element de la matriu.

161
00:07:07,920 --> 00:07:10,250
>> Quin és el punt mig d'aquest conjunt?

162
00:07:10,250 --> 00:07:13,459
Bé, comença a les 8, que
acaba a les 8, el punt mig és 8.

163
00:07:13,459 --> 00:07:14,750
¿Això és el que estem buscant?

164
00:07:14,750 --> 00:07:16,339
Estem buscant 17?

165
00:07:16,339 --> 00:07:17,380
No, estem a la recerca de 16.

166
00:07:17,380 --> 00:07:20,160
Així que si existeix en la matriu,
ha d'existir en algun lloc

167
00:07:20,160 --> 00:07:21,935
a l'esquerra d'on actualment som.

168
00:07:21,935 --> 00:07:23,060
Llavors, què farem?

169
00:07:23,060 --> 00:07:26,610
Bé, anem a establir el punt final a ser només
a l'esquerra del punt mitjà actual.

170
00:07:26,610 --> 00:07:29,055
Així que anem a canviar el punt final a 7.

171
00:07:29,055 --> 00:07:32,120
Veus el que acaba de
que va passar aquí, però?

172
00:07:32,120 --> 00:07:33,370
Busqui aquí ara.

173
00:07:33,370 --> 00:07:35,970
>> Start és ara més gran que fi.

174
00:07:35,970 --> 00:07:39,620
Efectivament, els dos extrems
de la nostra gamma han creuat,

175
00:07:39,620 --> 00:07:42,252
i el punt d'inici és
ara després que el punt final.

176
00:07:42,252 --> 00:07:43,960
Bé, això no ho fa
té sentit, oi?

177
00:07:43,960 --> 00:07:47,960
Així que ara, el que podem dir és que
tenir una matriu de mida sub 0.

178
00:07:47,960 --> 00:07:50,110
I una vegada que estem arribat a
aquest punt, podem ara

179
00:07:50,110 --> 00:07:53,940
garantir que l'element 16
no existeix en la matriu,

180
00:07:53,940 --> 00:07:56,280
pel fet que el punt de partida
i el punt final han creuat.

181
00:07:56,280 --> 00:07:58,340
I pel que no hi és.

182
00:07:58,340 --> 00:08:01,340
Ara, observi que això és lleugerament
diferent a la del punt d'inici i fi

183
00:08:01,340 --> 00:08:02,900
punt que es trobi el mateix.

184
00:08:02,900 --> 00:08:05,030
Si haguéssim estat buscant
pel 17, tindria

185
00:08:05,030 --> 00:08:08,870
estat de la matriu, i el punt d'inici
i el punt final de l'última iteració

186
00:08:08,870 --> 00:08:11,820
abans que aquests punts creuats,
hauríem trobat 17 allà.

187
00:08:11,820 --> 00:08:15,510
És només quan creuen que podem
garanteix que l'element no

188
00:08:15,510 --> 00:08:17,180
existir en la matriu.

189
00:08:17,180 --> 00:08:20,260
>> Així que anem a fer molt menys
passos que la recerca lineal.

190
00:08:20,260 --> 00:08:23,250
En el pitjor dels casos, vam tenir
per dividir una llista de n elements

191
00:08:23,250 --> 00:08:27,770
en repetides ocasions per la meitat per trobar l'objectiu,
ja sigui perquè l'element de destinació

192
00:08:27,770 --> 00:08:33,110
serà en algun lloc de l'última
divisió, o no existeix en absolut.

193
00:08:33,110 --> 00:08:37,830
Així que en el pitjor dels casos, hem de
dividir el array-- ho saps?

194
00:08:37,830 --> 00:08:40,510
Iniciar sessió de n vegades; nosaltres
haver de tallar el problema

195
00:08:40,510 --> 00:08:42,610
enmig d'un cert nombre de vegades.

196
00:08:42,610 --> 00:08:45,160
Aquest nombre de vegades que és log n.

197
00:08:45,160 --> 00:08:46,510
>> Quin és el millor dels casos?

198
00:08:46,510 --> 00:08:48,899
Bé, la primera vegada que
calcular el punt mitjà,

199
00:08:48,899 --> 00:08:50,190
trobem el que estem buscant.

200
00:08:50,190 --> 00:08:52,150
En tot l'anterior
exemples de recerca binària

201
00:08:52,150 --> 00:08:55,489
que acabem anat, si tinguéssim
estat buscant l'element 15,

202
00:08:55,489 --> 00:08:57,030
hauríem trobat que immediatament.

203
00:08:57,030 --> 00:08:58,321
Això va ser al principi.

204
00:08:58,321 --> 00:09:01,200
Aquest va ser el punt mig de
el primer intent d'una divisió

205
00:09:01,200 --> 00:09:03,950
d'una divisió en la recerca binària.

206
00:09:03,950 --> 00:09:06,350
>> I així, en el pitjor
cas, la recerca binària funciona

207
00:09:06,350 --> 00:09:11,580
en el registre de n, que és substancialment millor
de recerca lineal, en el pitjor dels casos.

208
00:09:11,580 --> 00:09:16,210
En el millor cas, binari
recerca s'executa en l'omega d'1.

209
00:09:16,210 --> 00:09:18,990
Així que la recerca binària és molt
millor que la recerca lineal,

210
00:09:18,990 --> 00:09:23,270
però vostè ha de tractar amb el procés de
ordenar la matriu abans de poder

211
00:09:23,270 --> 00:09:26,140
aprofitar el poder de cerca binària.

212
00:09:26,140 --> 00:09:27,130
>> Sóc Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Això és CS 50.

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