1
00:00:00,000 --> 00:00:03,346
>> [Prehrávanie hudby]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Dobre.

4
00:00:06,220 --> 00:00:08,140
Takže binárne vyhľadávanie je
Algoritmus môžeme použiť

5
00:00:08,140 --> 00:00:10,530
nájsť prvok vnútri poľa.

6
00:00:10,530 --> 00:00:14,710
Na rozdiel od lineárnej hľadania, to vyžaduje
Osobitná podmienka byť splnená vopred,

7
00:00:14,710 --> 00:00:19,020
ale je to oveľa účinnejšie, ak
táto podmienka je, v skutočnosti, sa stretol.

8
00:00:19,020 --> 00:00:20,470
>> Takže to, čo je tu nápad?

9
00:00:20,470 --> 00:00:21,780
je to rozdeľ a panuj.

10
00:00:21,780 --> 00:00:25,100
Chceme znížiť veľkosť
oblasť hľadania o polovicu každý čas

11
00:00:25,100 --> 00:00:27,240
s cieľom nájsť cieľové číslo.

12
00:00:27,240 --> 00:00:29,520
To je miesto, kde táto podmienka
prichádza do hry, hoci.

13
00:00:29,520 --> 00:00:32,740
Môžeme využiť iba silu
odstránenie polovice prvkov

14
00:00:32,740 --> 00:00:36,070
bez pri pohľade na
je v prípade, že pole sa triedi.

15
00:00:36,070 --> 00:00:39,200
>> Ak je to úplný mix up,
Nemôžeme len tak z ruky

16
00:00:39,200 --> 00:00:42,870
zbaviť polovica prvkov, pretože
nevieme, čo sme vyradenie.

17
00:00:42,870 --> 00:00:45,624
Ale v prípade, že pole je radený,
môžeme to urobiť, pretože sme

18
00:00:45,624 --> 00:00:48,040
viem, že všetko, čo k
vľavo, kde sme v súčasnej dobe sú

19
00:00:48,040 --> 00:00:50,500
musí byť nižšia, než je
Hodnota sme v súčasnosti.

20
00:00:50,500 --> 00:00:52,300
A všetko, čo k
právo na to, kde sme

21
00:00:52,300 --> 00:00:55,040
musí byť väčšia ako hodnota
sme v súčasnosti pri pohľade na.

22
00:00:55,040 --> 00:00:58,710
>> Takže čo je pseudokód
kroky pre binárne vyhľadávanie?

23
00:00:58,710 --> 00:01:02,310
Tento postup opakujeme, kým nebude
poľa alebo, ako budeme postupovať cez,

24
00:01:02,310 --> 00:01:07,740
podsouborům, menšie kusy
pôvodnej poľa je veľkosti 0.

25
00:01:07,740 --> 00:01:10,960
Vypočítajte polovicu
aktuálneho podsúboru.

26
00:01:10,960 --> 00:01:14,460
>> Ak je hodnota hľadáte, je
v tomto prvku poľa, zastaviť.

27
00:01:14,460 --> 00:01:15,030
Našiel si to.

28
00:01:15,030 --> 00:01:16,550
To je skvelé.

29
00:01:16,550 --> 00:01:19,610
Inak, ak je cieľ
menej než to, čo je v strede,

30
00:01:19,610 --> 00:01:23,430
takže ak hodnoty pozeráme
pre nižšie, ako to, čo vidíme,

31
00:01:23,430 --> 00:01:26,780
tento proces opakovať, ale
zmeniť koncový bod, namiesto toho

32
00:01:26,780 --> 00:01:29,300
z toho, že pôvodná
dokončiť celou radou,

33
00:01:29,300 --> 00:01:34,110
byť len na ľavej strane
kde sme sa len pozrel.

34
00:01:34,110 --> 00:01:38,940
>> Vedeli sme, že prostredný bola príliš vysoká,
alebo cieľovú bol menší, ako v stredu,

35
00:01:38,940 --> 00:01:42,210
a tak, že musí existovať, ak je to
vôbec existuje, v poli,

36
00:01:42,210 --> 00:01:44,660
niekde na ľavej strane stredového bodu.

37
00:01:44,660 --> 00:01:48,120
A tak sme si nastaviť pole
poloha len na ľavej strane

38
00:01:48,120 --> 00:01:51,145
midpoint ako nového koncového bodu.

39
00:01:51,145 --> 00:01:53,770
Naopak, ak je cieľ
väčšie, než to, čo je v strede,

40
00:01:53,770 --> 00:01:55,750
urobíme presne rovnaký
proces, ale namiesto toho

41
00:01:55,750 --> 00:01:59,520
zmeniť počiatočný bod, aby
len na pravej strane stredu

42
00:01:59,520 --> 00:02:00,680
sme jednoducho počítať.

43
00:02:00,680 --> 00:02:03,220
A potom sme sa znovu začať proces.

44
00:02:03,220 --> 00:02:05,220
>> Poďme si predstaviť to, OK?

45
00:02:05,220 --> 00:02:08,620
Takže je tu veľa deje, a na tú,
ale tu je rad z 15 elementov.

46
00:02:08,620 --> 00:02:11,400
A budeme sa sledovanie
o oveľa viac vecí tentoraz.

47
00:02:11,400 --> 00:02:13,870
Takže lineárne hľadanie, my sme boli
len sa starať o cieľ.

48
00:02:13,870 --> 00:02:15,869
Ale tentoraz chceme
starostlivosť o tom, kde sme

49
00:02:15,869 --> 00:02:18,480
začína vyzerať, kde
zastavujeme hľadáte,

50
00:02:18,480 --> 00:02:21,876
a čo je na stred
aktuálneho poľa.

51
00:02:21,876 --> 00:02:23,250
Tak ideme na to s binárne vyhľadávanie.

52
00:02:23,250 --> 00:02:25,290
Sme skoro dobré ísť, nie?

53
00:02:25,290 --> 00:02:28,650
Ja som jednoducho ísť dať dole
nižšie tu množina indexov.

54
00:02:28,650 --> 00:02:32,430
To je v podstate to, čo práve element
matice hovoríme.

55
00:02:32,430 --> 00:02:34,500
S lineárne hľadanie, my
starostlivosti, pretože my

56
00:02:34,500 --> 00:02:36,800
Potrebujeme vedieť, koľko
prvky, my iterácie cez,

57
00:02:36,800 --> 00:02:40,010
ale nemáme vlastne jedno, čo
element sme v súčasnosti pri pohľade na.

58
00:02:40,010 --> 00:02:41,014
V binárne hľadanie, čo robíme.

59
00:02:41,014 --> 00:02:42,930
A tak to sú len
tam ako malý sprievodca.

60
00:02:42,930 --> 00:02:44,910
>> Takže môžeme začať, nie?

61
00:02:44,910 --> 00:02:46,240
No, nie tak celkom.

62
00:02:46,240 --> 00:02:48,160
Spomeň si, čo som povedal,
o binárneho vyhľadávania?

63
00:02:48,160 --> 00:02:50,955
Nemôžeme to urobiť na
netriedený poľa alebo inak,

64
00:02:50,955 --> 00:02:55,820
nie sme zaručiť, že
určité prvky alebo hodnoty nie sú

65
00:02:55,820 --> 00:02:57,650
náhodnému
vypustí, keď sme práve

66
00:02:57,650 --> 00:02:59,920
rozhodnúť ignorovať polovicu poľa.

67
00:02:59,920 --> 00:03:02,574
>> Takže prvý krok s binárne vyhľadávanie
je musíte mať zoradené poľa.

68
00:03:02,574 --> 00:03:05,240
A môžete použiť niektorý z triedenia
algoritmy sme hovorili o

69
00:03:05,240 --> 00:03:06,700
aby ste sa dostali do tejto pozície.

70
00:03:06,700 --> 00:03:10,370
Takže teraz, sme v pozícii, kedy
môžeme vykonávať binárne vyhľadávanie.

71
00:03:10,370 --> 00:03:12,560
>> Takže poďme proces opakovať
krok za krokom a držať

72
00:03:12,560 --> 00:03:14,830
sledovať, čo sa deje, ako sme ísť.

73
00:03:14,830 --> 00:03:17,980
Takže najprv musíme urobiť, je výpočet
stred z existujúceho poľa.

74
00:03:17,980 --> 00:03:20,620
No, budeme sa povedať, že sme v prvom rade
všetci, hľadá pre hodnotu 19.

75
00:03:20,620 --> 00:03:22,290
Snažíme sa nájsť číslo 19.

76
00:03:22,290 --> 00:03:25,380
Prvým prvkom tejto
poľa je umiestnený na indexe nula,

77
00:03:25,380 --> 00:03:28,880
a posledný prvok tejto
poľa je umiestnený na indexe 14.

78
00:03:28,880 --> 00:03:31,430
A tak budeme hovoriť tie začiatok a koniec.

79
00:03:31,430 --> 00:03:35,387
>> Takže sme vypočítať stred strany
pridaním 0 a navyše 14 deleno 2;

80
00:03:35,387 --> 00:03:36,720
celkom jednoduché stred.

81
00:03:36,720 --> 00:03:40,190
A môžeme povedať, že
stred je teraz 7.

82
00:03:40,190 --> 00:03:43,370
Takže je 15 to, čo hľadáme?

83
00:03:43,370 --> 00:03:43,940
Nie to nie je.

84
00:03:43,940 --> 00:03:45,270
Hľadáme 19.

85
00:03:45,270 --> 00:03:49,400
Ale my vieme, že 19 je väčšia
ako to, čo sme našli v stredu.

86
00:03:49,400 --> 00:03:52,470
>> Takže to, čo môžeme urobiť, je
zmeniť počiatočný bod

87
00:03:52,470 --> 00:03:57,280
byť len napravo od
stred, a znovu proces opakovať.

88
00:03:57,280 --> 00:04:01,690
A keď to urobíme, môžeme teraz povedať,
Nový začiatok bod je umiestnenie poľa 8.

89
00:04:01,690 --> 00:04:07,220
To, čo sme skutočne urobili, je
ignoroval všetko na ľavej strane 15.

90
00:04:07,220 --> 00:04:09,570
Odstránili sme polovicu
problému, a teraz,

91
00:04:09,570 --> 00:04:13,510
namiesto toho, aby musel vyhľadávať
viac ako 15 prvkov v našom poli,

92
00:04:13,510 --> 00:04:15,610
máme len hľadať cez 7.

93
00:04:15,610 --> 00:04:17,706
Takže 8 je nový východiskový bod.

94
00:04:17,706 --> 00:04:19,600
14 je stále koncový bod.

95
00:04:19,600 --> 00:04:21,430
>> A teraz sme sa prejsť znovu.

96
00:04:21,430 --> 00:04:22,810
Počítame nový stred.

97
00:04:22,810 --> 00:04:27,130
8 a 14, je 22, deleno 2, je 11.

98
00:04:27,130 --> 00:04:28,660
Je to to, čo hľadáme?

99
00:04:28,660 --> 00:04:30,110
Nie to nie je.

100
00:04:30,110 --> 00:04:32,930
Hľadáme hodnotu, ktorá je
menej, než to, čo sme našli.

101
00:04:32,930 --> 00:04:34,721
Takže budeme opakovať
opäť proces.

102
00:04:34,721 --> 00:04:38,280
Chystáme sa zmeniť koncový bod na
byť len na ľavej strane stredu.

103
00:04:38,280 --> 00:04:41,800
Takže nový koncový bod sa stane 10.

104
00:04:41,800 --> 00:04:44,780
A teraz, to je len časť
pole musíme usporiadať.

105
00:04:44,780 --> 00:04:48,460
Takže sme teraz odstránené
12 z 15 prvkov.

106
00:04:48,460 --> 00:04:51,550
Vieme, že v prípade 19
existuje v poli, to

107
00:04:51,550 --> 00:04:57,210
musí existovať niekde medzi prvkom
číslo 8 a prvok číslo 10.

108
00:04:57,210 --> 00:04:59,400
>> Takže sme vypočítať nový stred znova.

109
00:04:59,400 --> 00:05:02,900
8 a 10, je 18, deleno 2 je 9.

110
00:05:02,900 --> 00:05:05,074
A v tomto prípade, pozrite sa
Cieľom je u stredu.

111
00:05:05,074 --> 00:05:06,740
Našli sme presne to, čo hľadáme.

112
00:05:06,740 --> 00:05:07,780
Môžeme sa zastaviť.

113
00:05:07,780 --> 00:05:10,561
Úspešne sme dokončili
binárne vyhľadávanie.

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

115
00:05:11,060 --> 00:05:13,930
Takže vieme, tento algoritmus
funguje, ak je cieľ

116
00:05:13,930 --> 00:05:16,070
niekde vo vnútri matice.

117
00:05:16,070 --> 00:05:19,060
Má tento algoritmus pracovať, pokiaľ
cieľ nie je v poli?

118
00:05:19,060 --> 00:05:20,810
No, začnime to
znova, a tentoraz,

119
00:05:20,810 --> 00:05:23,380
pozrime sa aj na prvku
16, ktorý vizuálne vidíme

120
00:05:23,380 --> 00:05:25,620
neexistuje nikde v matici.

121
00:05:25,620 --> 00:05:27,110
>> Počiatočný bod je opäť 0.

122
00:05:27,110 --> 00:05:28,590
Konečný bod je opäť 14.

123
00:05:28,590 --> 00:05:32,490
Tí, ktorí sú indexy prvý a
posledná prvky kompletného poľa.

124
00:05:32,490 --> 00:05:36,057
A pôjdeme cez proces sme práve
Znovu prešiel a snažil sa nájsť 16,

125
00:05:36,057 --> 00:05:39,140
aj keď vizuálne, môžeme už
povedať, že to nebude tam.

126
00:05:39,140 --> 00:05:43,450
Chceme len, aby sa uistil, tento algoritmus
bude v skutočnosti, stále pracovať určitým spôsobom

127
00:05:43,450 --> 00:05:46,310
a nie len opustiť nás
uviazol v nekonečnej slučke.

128
00:05:46,310 --> 00:05:48,190
>> Takže to, čo je prvý krok?

129
00:05:48,190 --> 00:05:50,230
Vypočítajte polovicu
aktuálneho poľa.

130
00:05:50,230 --> 00:05:52,790
Čo je to stred
súčasné pole?

131
00:05:52,790 --> 00:05:54,410
No, je to 7, nie?

132
00:05:54,410 --> 00:05:57,560
14 a 0 deleno 2 je 7.

133
00:05:57,560 --> 00:05:59,280
Je 15 to, čo hľadáme?

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

135
00:05:59,780 --> 00:06:02,930
Je to celkom blízko, ale my hľadáme
pre hodnotu o niečo väčší, než je.

136
00:06:02,930 --> 00:06:06,310
>> Takže vieme, že to bude
byť nikde na ľavej strane 15.

137
00:06:06,310 --> 00:06:08,540
Cieľom je väčšia než
čo je v strede.

138
00:06:08,540 --> 00:06:12,450
A tak sme si stanovili nový počiatočný bod na
byť len vpravo od stredu.

139
00:06:12,450 --> 00:06:16,130
Stred je v súčasnej dobe 7, takže
povedzme, že nový začiatok bod 8.

140
00:06:16,130 --> 00:06:18,130
A to, čo sme skutočne som
opäť urobil je ignorovaný

141
00:06:18,130 --> 00:06:21,150
celá ľavá polovica matice.

142
00:06:21,150 --> 00:06:23,750
>> Teraz sme opakovať
spracovať ešte raz.

143
00:06:23,750 --> 00:06:24,910
Vypočítajte nový stred.

144
00:06:24,910 --> 00:06:29,350
8 a 14, je 22, deleno 2, je 11.

145
00:06:29,350 --> 00:06:31,060
Je 23 to, čo hľadáme?

146
00:06:31,060 --> 00:06:31,870
Bohužiaľ nie.

147
00:06:31,870 --> 00:06:34,930
Hľadáme hodnotu
ktorá je menšia ako 23.

148
00:06:34,930 --> 00:06:37,850
A tak v tomto prípade, ideme
zmeniť koncový bod byť spravodlivý

149
00:06:37,850 --> 00:06:40,035
naľavo od aktuálneho stredového bodu.

150
00:06:40,035 --> 00:06:43,440
Súčasný stred je 11, a
takže budeme nastaviť nový koncový bod

151
00:06:43,440 --> 00:06:46,980
pre nabudúce ideme
v tomto procese až 10.

152
00:06:46,980 --> 00:06:48,660
>> Opäť sme prejsť procesom znova.

153
00:06:48,660 --> 00:06:49,640
Vypočítajte stred.

154
00:06:49,640 --> 00:06:53,100
8 a 10 deleno 2 je 9.

155
00:06:53,100 --> 00:06:54,750
Je 19 to, čo hľadáme?

156
00:06:54,750 --> 00:06:55,500
Bohužiaľ nie.

157
00:06:55,500 --> 00:06:58,050
Stále hľadáme
číslo menšie, než je.

158
00:06:58,050 --> 00:07:02,060
Takže budeme meniť koncového bodu, tentoraz
byť len na ľavej strane od stredu.

159
00:07:02,060 --> 00:07:05,532
Stred je v súčasnej dobe 9,
takže koncový bod bude 8.

160
00:07:05,532 --> 00:07:07,920
A teraz, my sme len sa pozerá
v jednom prvku poľa.

161
00:07:07,920 --> 00:07:10,250
>> Čo je stred tohto poľa?

162
00:07:10,250 --> 00:07:13,459
No, to začína v 8, je
končí v 8, stred je 8.

163
00:07:13,459 --> 00:07:14,750
Je to to, čo hľadáme?

164
00:07:14,750 --> 00:07:16,339
Hľadáme 17?

165
00:07:16,339 --> 00:07:17,380
Nie, my hľadáme pre 16.

166
00:07:17,380 --> 00:07:20,160
Takže ak existuje v poli,
že musí existovať niekde

167
00:07:20,160 --> 00:07:21,935
na ľavej strane, kde sú v súčasnej dobe.

168
00:07:21,935 --> 00:07:23,060
Tak čo budeme robiť?

169
00:07:23,060 --> 00:07:26,610
No, budeme nastavenie koncového bodu, aby len
naľavo od aktuálneho stredového bodu.

170
00:07:26,610 --> 00:07:29,055
Takže budeme chcete zmeniť koncový bod až 7.

171
00:07:29,055 --> 00:07:32,120
Vidíte, čo sa práve
tu stalo, aj keď?

172
00:07:32,120 --> 00:07:33,370
Pozrite sa tu.

173
00:07:33,370 --> 00:07:35,970
>> Štart je teraz väčšia ako koniec.

174
00:07:35,970 --> 00:07:39,620
Účinne, sú oba konce
z našej ponuku prekročili,

175
00:07:39,620 --> 00:07:42,252
a počiatočný bod je
Teraz po koncový bod.

176
00:07:42,252 --> 00:07:43,960
No, to nie je
nejaký zmysel, že jo?

177
00:07:43,960 --> 00:07:47,960
Takže teraz, čo môžeme povedať, je, že sme
majú čiastkové pole veľkosti 0.

178
00:07:47,960 --> 00:07:50,110
A akonáhle sme dostali do
tento bod, môžeme teraz

179
00:07:50,110 --> 00:07:53,940
zaručiť, že prvok 16
neexistuje v matici,

180
00:07:53,940 --> 00:07:56,280
preto, že východiskový bod
a koncový bod, ktoré prekročili.

181
00:07:56,280 --> 00:07:58,340
A tak je to tam nie je.

182
00:07:58,340 --> 00:08:01,340
Teraz, všimnite si, že je to trochu
líši od počiatočného bodu a na konci

183
00:08:01,340 --> 00:08:02,900
bod je rovnaký.

184
00:08:02,900 --> 00:08:05,030
Keby sme hľadali
pre 17, malo by to

185
00:08:05,030 --> 00:08:08,870
bol v poli, a počiatočný bod
a koncový bod tej poslednej iterácie

186
00:08:08,870 --> 00:08:11,820
Než tie body prešiel,
by sme našli 17 tam.

187
00:08:11,820 --> 00:08:15,510
Je to len vtedy, keď prekročí, že môžeme
zaručiť, že element nie je

188
00:08:15,510 --> 00:08:17,180
existujú v matici.

189
00:08:17,180 --> 00:08:20,260
>> Takže poďme sa veľa menej
Kroky než lineárne hľadania.

190
00:08:20,260 --> 00:08:23,250
V najhoršom prípade, mali sme
rozdeliť sa ustanovuje zoznam n elementy

191
00:08:23,250 --> 00:08:27,770
opakovane na polovicu nájsť cieľ,
a to buď preto, že cieľový prvok

192
00:08:27,770 --> 00:08:33,110
bude niekde v poslednej
divízie, alebo neexistuje vôbec.

193
00:08:33,110 --> 00:08:37,830
Takže v najhoršom prípade, musíme
rozišli sa array-- to viete?

194
00:08:37,830 --> 00:08:40,510
Logn časy; my
musieť znížiť problém

195
00:08:40,510 --> 00:08:42,610
v polovici určitého počtu čias.

196
00:08:42,610 --> 00:08:45,160
To, koľkokrát je log n.

197
00:08:45,160 --> 00:08:46,510
>> Aký je najlepší scenár?

198
00:08:46,510 --> 00:08:48,899
No, prvýkrát, keď sme
vypočítať stred,

199
00:08:48,899 --> 00:08:50,190
nájdeme to, čo hľadáme.

200
00:08:50,190 --> 00:08:52,150
Vo všetkých predchádzajúca
príklady na binárne vyhľadávanie

201
00:08:52,150 --> 00:08:55,489
sme práve preberali, keby sme mali
Hľadal prvku 15,

202
00:08:55,489 --> 00:08:57,030
by sme zistili, že okamžite.

203
00:08:57,030 --> 00:08:58,321
To bolo na samom začiatku.

204
00:08:58,321 --> 00:09:01,200
To bol stred
Prvý pokus o rozdelení

205
00:09:01,200 --> 00:09:03,950
z divízie v binárnom vyhľadávania.

206
00:09:03,950 --> 00:09:06,350
>> A tak v najhoršom
Prípad, binárne vyhľadávanie beží

207
00:09:06,350 --> 00:09:11,580
v log n, čo je podstatne lepší
než lineárne vyhľadávanie, v najhoršom prípade.

208
00:09:11,580 --> 00:09:16,210
V najlepšom prípade, binárne
Vyhľadávanie prebieha v omega 1.

209
00:09:16,210 --> 00:09:18,990
Takže binárne vyhľadávanie je veľa
lepšie ako lineárne vyhľadávanie,

210
00:09:18,990 --> 00:09:23,270
ale budete musieť vysporiadať s procesom
triedenie svoje polia skôr, než si môžete

211
00:09:23,270 --> 00:09:26,140
využiť silu binárneho vyhľadávania.

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

213
00:09:27,130 --> 00:09:29,470
To je CS 50.

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