1
00:00:00,000 --> 00:00:03,346
>> [Predvaja glasba]

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

3
00:00:05,258 --> 00:00:06,220
>> Doug LLOYD: V redu.

4
00:00:06,220 --> 00:00:08,140
Torej, binarno iskanje je
Algoritem lahko uporabimo

5
00:00:08,140 --> 00:00:10,530
poiščite element znotraj matrike.

6
00:00:10,530 --> 00:00:14,710
Za razliko od linearnega iskanja, se zahteva
Poseben pogoj je izpolnjen vnaprej,

7
00:00:14,710 --> 00:00:19,020
ampak to je tako veliko bolj učinkovito, če
da je pogoj, dejansko izpolnjeni.

8
00:00:19,020 --> 00:00:20,470
>> Torej, kaj je ideja tukaj?

9
00:00:20,470 --> 00:00:21,780
to je deli in vladaj.

10
00:00:21,780 --> 00:00:25,100
Želimo zmanjšati velikost
iskanje območje, ki ga pol vsak čas

11
00:00:25,100 --> 00:00:27,240
da bi imel ciljno številko.

12
00:00:27,240 --> 00:00:29,520
To je, če ta pogoj
pride v poštev, čeprav.

13
00:00:29,520 --> 00:00:32,740
Mi lahko izkoristite samo moč
odpravo polovica elementov

14
00:00:32,740 --> 00:00:36,070
celo brez gledaš
jih, če je matrika razporejene.

15
00:00:36,070 --> 00:00:39,200
>> Če je popoln mix up,
Ne moremo samo iz roke

16
00:00:39,200 --> 00:00:42,870
zavreči polovica elementov, ker
ne vemo, kaj smo se zavrže.

17
00:00:42,870 --> 00:00:45,624
Ampak, če je matrika razporejene,
bomo lahko to storili, ker smo

18
00:00:45,624 --> 00:00:48,040
vem, da je vse, kar je
levo, kjer smo trenutno so

19
00:00:48,040 --> 00:00:50,500
sme biti nižja od
Vrednost smo trenutno.

20
00:00:50,500 --> 00:00:52,300
In vse, kar je na
Pravica do kje smo

21
00:00:52,300 --> 00:00:55,040
mora biti večja od vrednosti
smo trenutno iščejo.

22
00:00:55,040 --> 00:00:58,710
>> Torej, kaj je psevdokoda
koraki za binarnem iskanju?

23
00:00:58,710 --> 00:01:02,310
Mi ta postopek ponovite, dokler
niz ali, kot smo nadaljevali skozi,

24
00:01:02,310 --> 00:01:07,740
sub nizi, manjših kosov
prvotna matrika, je velikosti 0.

25
00:01:07,740 --> 00:01:10,960
Izračunamo srednjo vrednost
trenutnega pod paleto.

26
00:01:10,960 --> 00:01:14,460
>> Če je vrednost, ki jo iščete,
V tem elementu matrike, stop.

27
00:01:14,460 --> 00:01:15,030
Našli ste jo.

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

29
00:01:16,550 --> 00:01:19,610
V nasprotnem primeru, če je cilj
manj od tistega, kar je na sredini,

30
00:01:19,610 --> 00:01:23,430
tako da, če vrednost iščeva
za je nižja od tega, kar smo videli,

31
00:01:23,430 --> 00:01:26,780
Ta postopek ponovite, vendar
spremeniti končno točko, namesto

32
00:01:26,780 --> 00:01:29,300
o čemer je prvotna
dokončati celotno paleto,

33
00:01:29,300 --> 00:01:34,110
da je samo na levi
kje smo pravkar pogledal.

34
00:01:34,110 --> 00:01:38,940
>> Vedeli smo, da je bil srednji previsoka,
ali cilj je bil manjši od sredine,

35
00:01:38,940 --> 00:01:42,210
in zato mora obstajati, če to
sploh obstaja v matriki,

36
00:01:42,210 --> 00:01:44,660
nekje na levi sredini.

37
00:01:44,660 --> 00:01:48,120
In tako bomo nastavili niz
lokacija samo na levi

38
00:01:48,120 --> 00:01:51,145
od središčne točke kot novi končno točko.

39
00:01:51,145 --> 00:01:53,770
Nasprotno pa, če je cilj
večji od tistega, kar je na sredini,

40
00:01:53,770 --> 00:01:55,750
počnemo popolnoma enaka
Postopek, ampak smo

41
00:01:55,750 --> 00:01:59,520
spremenite začetno točko, da bo
Samo na desni strani središčne

42
00:01:59,520 --> 00:02:00,680
smo samo izračunati.

43
00:02:00,680 --> 00:02:03,220
In potem smo spet začeti proces.

44
00:02:03,220 --> 00:02:05,220
>> Oglejmo vizualizirati to v redu?

45
00:02:05,220 --> 00:02:08,620
Torej je veliko dogaja in tukaj,
ampak tu je niz 15 elementov.

46
00:02:08,620 --> 00:02:11,400
In bomo se sledenja
za veliko več stvari tokrat.

47
00:02:11,400 --> 00:02:13,870
Torej, v linearno iskanje, smo bili
samo skrbeti tarčo.

48
00:02:13,870 --> 00:02:15,869
Toda tokrat smo želeli
briga kje smo

49
00:02:15,869 --> 00:02:18,480
začeli gledati, kje
smo se ustavili v prihodnost,

50
00:02:18,480 --> 00:02:21,876
in kaj je sredina
trenutnega niza.

51
00:02:21,876 --> 00:02:23,250
Torej gremo z binarno iskanje.

52
00:02:23,250 --> 00:02:25,290
Mi smo precej na dobri poti, kajne?

53
00:02:25,290 --> 00:02:28,650
Jaz sem le, da bo odložil
Spodaj tukaj niz indeksov.

54
00:02:28,650 --> 00:02:32,430
To je v bistvu samo tisto element
array smo govoriš.

55
00:02:32,430 --> 00:02:34,500
Z linearno iskanje, smo
skrbi, saj mi

56
00:02:34,500 --> 00:02:36,800
morate vedeti, koliko
Elementi smo ponavljanjem več,

57
00:02:36,800 --> 00:02:40,010
ampak pravzaprav ne zanima, kaj
element smo trenutno iščejo.

58
00:02:40,010 --> 00:02:41,014
V binarnem iskanju, počnemo.

59
00:02:41,014 --> 00:02:42,930
In tako tistih, ki so samo
tam malo vodilo.

60
00:02:42,930 --> 00:02:44,910
>> Tako bomo lahko začeli, kajne?

61
00:02:44,910 --> 00:02:46,240
No, ne povsem.

62
00:02:46,240 --> 00:02:48,160
Se spomniš, kaj sem rekel
o binarnem iskanju?

63
00:02:48,160 --> 00:02:50,955
Ne moremo storiti opravljena na
razvrščeni matrika ali pa,

64
00:02:50,955 --> 00:02:55,820
ne bomo zagotovili, da
nekateri elementi ali vrednosti niso

65
00:02:55,820 --> 00:02:57,650
nenamerne
zavržejo, ko smo tik

66
00:02:57,650 --> 00:02:59,920
odloči, da prezreti polovica array.

67
00:02:59,920 --> 00:03:02,574
>> Torej en korak z binarno iskanje
je, da mora imeti sortira paleto.

68
00:03:02,574 --> 00:03:05,240
In jih lahko uporabite katero koli od razvrščanje
algoritmi smo govorili

69
00:03:05,240 --> 00:03:06,700
da boste dobili na ta položaj.

70
00:03:06,700 --> 00:03:10,370
Torej sedaj, smo v položaju, kjer je
bomo lahko opravljajo binarno iskanje.

71
00:03:10,370 --> 00:03:12,560
>> Torej, kaj je ponoviti postopek
korak za korakom in vodi

72
00:03:12,560 --> 00:03:14,830
Spremljajte, kaj se dogaja, ko gremo.

73
00:03:14,830 --> 00:03:17,980
Torej najprej moramo storiti, je izračun
razpolovišča tekočega matrike.

74
00:03:17,980 --> 00:03:20,620
No, bomo rekli, da smo v prvi vrsti
vsem, ki iščejo v vrednosti 19.

75
00:03:20,620 --> 00:03:22,290
Poskušamo najti številko 19.

76
00:03:22,290 --> 00:03:25,380
Prvi element tega
Niz se nahaja na indeksu ničlo,

77
00:03:25,380 --> 00:03:28,880
in zadnji element tega
Niz se nahaja na indeks 14.

78
00:03:28,880 --> 00:03:31,430
In tako bomo pozivajo tiste, začetek in konec.

79
00:03:31,430 --> 00:03:35,387
>> Tako smo izračunali srednjo vrednost s
dodajanje 0 plus 14 deljeno z 2;

80
00:03:35,387 --> 00:03:36,720
precej preprosta sredina.

81
00:03:36,720 --> 00:03:40,190
In lahko rečemo, da
sredina je zdaj 7.

82
00:03:40,190 --> 00:03:43,370
Torej je 15, kar iščemo?

83
00:03:43,370 --> 00:03:43,940
Ne, ni.

84
00:03:43,940 --> 00:03:45,270
Iščemo 19.

85
00:03:45,270 --> 00:03:49,400
Vendar vemo, da je 19 več
od tistega, kar smo našli na sredini.

86
00:03:49,400 --> 00:03:52,470
>> Torej, kaj lahko storimo, je,
spremenite začetno točko

87
00:03:52,470 --> 00:03:57,280
da je samo na desni strani
sredini in ponovite postopek.

88
00:03:57,280 --> 00:04:01,690
In ko bomo to storili, zdaj pravijo, da je
nova izhodiščna točka je matrika lokacija 8.

89
00:04:01,690 --> 00:04:07,220
Kaj smo dejansko storili, je
prezreti vse na levi strani 15.

90
00:04:07,220 --> 00:04:09,570
Mi smo odpraviti polovico
problema, zdaj,

91
00:04:09,570 --> 00:04:13,510
namesto da bi iskanje
več kot 15 elementov v naši matriki,

92
00:04:13,510 --> 00:04:15,610
imamo le iskati nad 7.

93
00:04:15,610 --> 00:04:17,706
Torej 8 je nov začetek, točka.

94
00:04:17,706 --> 00:04:19,600
14 je še vedno končna točka.

95
00:04:19,600 --> 00:04:21,430
>> In zdaj, gremo čez to še enkrat.

96
00:04:21,430 --> 00:04:22,810
Smo izračunali novo srednjo vrednost.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 je 22, deljeno z 2, je 11.

98
00:04:27,130 --> 00:04:28,660
Je to tisto, kar iščemo?

99
00:04:28,660 --> 00:04:30,110
Ne, ni.

100
00:04:30,110 --> 00:04:32,930
Iščemo za vrednost, ki je
manj od tistega, kar smo pravkar našel.

101
00:04:32,930 --> 00:04:34,721
Torej bomo ponovili
spet proces.

102
00:04:34,721 --> 00:04:38,280
Bomo spremenili končno točko do
ravno na levi sredini.

103
00:04:38,280 --> 00:04:41,800
Zato je novi končna točka postane 10.

104
00:04:41,800 --> 00:04:44,780
In zdaj, da je le del
array moramo, da razvrstite skozi.

105
00:04:44,780 --> 00:04:48,460
Tako smo zdaj odpravljena
12 od 15 elementov.

106
00:04:48,460 --> 00:04:51,550
Vemo, da če 19
obstaja v matriki, jo

107
00:04:51,550 --> 00:04:57,210
mora obstajati nekje med elementom
številka 8 in element številka 10.

108
00:04:57,210 --> 00:04:59,400
>> Torej smo spet izračunamo novo srednjo vrednost.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 je 18, deljeno z 2 je 9.

110
00:05:02,900 --> 00:05:05,074
In v tem primeru, poglej se
Cilj je na sredini.

111
00:05:05,074 --> 00:05:06,740
Našli smo točno tisto, kar smo iskali.

112
00:05:06,740 --> 00:05:07,780
Mi lahko ustavi.

113
00:05:07,780 --> 00:05:10,561
Uspešno smo zaključili
binarni iskanje.

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

115
00:05:11,060 --> 00:05:13,930
Torej vemo, ta algoritem
deluje, če je cilj

116
00:05:13,930 --> 00:05:16,070
nekje znotraj polja.

117
00:05:16,070 --> 00:05:19,060
Ali to algoritem deluje, če
ciljna ni v matriki?

118
00:05:19,060 --> 00:05:20,810
No, kaj je to začetek
še enkrat, in tokrat,

119
00:05:20,810 --> 00:05:23,380
Oglejmo si za element
16, ki je vizualno lahko vidimo

120
00:05:23,380 --> 00:05:25,620
ne obstaja nikjer v matriki.

121
00:05:25,620 --> 00:05:27,110
>> Začetna točka je spet 0.

122
00:05:27,110 --> 00:05:28,590
Končna točka je spet 14.

123
00:05:28,590 --> 00:05:32,490
Tisti, ki so indeksi prvi in
last elementi popolne nizu.

124
00:05:32,490 --> 00:05:36,057
In bomo šli skozi proces smo samo
šla skozi še enkrat, poskuša najti 16,

125
00:05:36,057 --> 00:05:39,140
čeprav vizualno, lahko smo že
povedal, da je ne bo tam.

126
00:05:39,140 --> 00:05:43,450
Pravkar smo želeli, da poskrbite, da ta algoritem
bo v resnici še vedno deluje na nek način

127
00:05:43,450 --> 00:05:46,310
in nas ne pustite
zaljubljen v neskončni zanki.

128
00:05:46,310 --> 00:05:48,190
>> Torej, kaj je prvi korak?

129
00:05:48,190 --> 00:05:50,230
Izračunamo srednjo vrednost
trenutnega niza.

130
00:05:50,230 --> 00:05:52,790
Kaj je sredina
trenutnega niz?

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

132
00:05:54,410 --> 00:05:57,560
14 plus 0 deljeno z 2 je 7.

133
00:05:57,560 --> 00:05:59,280
Je 15, kar iščemo?

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

135
00:05:59,780 --> 00:06:02,930
To je zelo blizu, ampak smo iskali
za vrednost nekoliko večji od tega.

136
00:06:02,930 --> 00:06:06,310
>> Tako smo vedeli, da se dogaja, da
nikjer na levi strani 15.

137
00:06:06,310 --> 00:06:08,540
Cilj je večja od
kaj je v sredini.

138
00:06:08,540 --> 00:06:12,450
In tako smo postavili novo začetno točko
ravno desno od sredine.

139
00:06:12,450 --> 00:06:16,130
Sredina je trenutno 7, tako da
recimo nova izhodiščna točka je 8.

140
00:06:16,130 --> 00:06:18,130
In kaj smo dejansko imel
spet naredil, je prezrta

141
00:06:18,130 --> 00:06:21,150
celotno levo polovico matrike.

142
00:06:21,150 --> 00:06:23,750
>> Zdaj smo ponovite
obdelati še enkrat.

143
00:06:23,750 --> 00:06:24,910
Izračunaj novo srednjo vrednost.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 je 22, deljeno z 2, je 11.

145
00:06:29,350 --> 00:06:31,060
Je 23, kar iščemo?

146
00:06:31,060 --> 00:06:31,870
Žal ne.

147
00:06:31,870 --> 00:06:34,930
Iščemo za vrednost
da je manj kot 23.

148
00:06:34,930 --> 00:06:37,850
In tako v tem primeru gremo
za spremembo končno točko, da je ravno

149
00:06:37,850 --> 00:06:40,035
levo od trenutnega sredini.

150
00:06:40,035 --> 00:06:43,440
Sedanji razpolovišča je 11, in
zato bomo določili novo končno točko

151
00:06:43,440 --> 00:06:46,980
za naslednjič, ko gremo
skozi ta proces do 10.

152
00:06:46,980 --> 00:06:48,660
>> Spet gremo skozi proces znova.

153
00:06:48,660 --> 00:06:49,640
Izračunamo srednjo vrednost.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 deljeno z 2 je 9.

155
00:06:53,100 --> 00:06:54,750
Je 19, kar iščemo?

156
00:06:54,750 --> 00:06:55,500
Žal ne.

157
00:06:55,500 --> 00:06:58,050
Mi smo še vedno išče
nekaj manj kot to.

158
00:06:58,050 --> 00:07:02,060
Torej bomo spremenili končne točke ta čas
da je samo na levi sredini.

159
00:07:02,060 --> 00:07:05,532
Sredina je trenutno 9,
tako da bo končna točka je 8.

160
00:07:05,532 --> 00:07:07,920
In sedaj, samo iščemo
na enem elementu matrike.

161
00:07:07,920 --> 00:07:10,250
>> Kaj je sredina tega polja?

162
00:07:10,250 --> 00:07:13,459
No, to se začne pri 8, je
konča na 8, sredina je 8.

163
00:07:13,459 --> 00:07:14,750
Je to tisto, kar iščemo?

164
00:07:14,750 --> 00:07:16,339
Iščemo za 17?

165
00:07:16,339 --> 00:07:17,380
Ne, iščemo 16.

166
00:07:17,380 --> 00:07:20,160
Torej, če obstaja v matriki,
mora obstajati nekje

167
00:07:20,160 --> 00:07:21,935
na levi strani, kjer smo trenutno so.

168
00:07:21,935 --> 00:07:23,060
Torej, kaj bomo storili?

169
00:07:23,060 --> 00:07:26,610
No, bomo nastavite končno točko, da je ravno
levo od trenutnega sredini.

170
00:07:26,610 --> 00:07:29,055
Torej bomo spremenili končno točko 7.

171
00:07:29,055 --> 00:07:32,120
Ali vidiš, kaj se je pravkar
se je tu zgodilo, čeprav?

172
00:07:32,120 --> 00:07:33,370
Poglej tukaj.

173
00:07:33,370 --> 00:07:35,970
>> Start je sedaj večja kot konec.

174
00:07:35,970 --> 00:07:39,620
Učinkovito, dva konca
naše matrike so prestopile,

175
00:07:39,620 --> 00:07:42,252
in izhodiščna točka je
zdaj po končni točki.

176
00:07:42,252 --> 00:07:43,960
No, da ne
nobenega smisla, kajne?

177
00:07:43,960 --> 00:07:47,960
Torej sedaj, kar lahko rečemo, je, da smo
imajo sub paleto velikosti 0.

178
00:07:47,960 --> 00:07:50,110
In ko smo gotten
ta točka, lahko sedaj smo

179
00:07:50,110 --> 00:07:53,940
jamčiti, da element 16
ne obstaja v matriki,

180
00:07:53,940 --> 00:07:56,280
ker začetno točko
in končna točka sta prečkala.

181
00:07:56,280 --> 00:07:58,340
In zato je ni tam.

182
00:07:58,340 --> 00:08:01,340
Zdaj, opazili, da je to nekoliko
drugačna kot začetno točko in na koncu

183
00:08:01,340 --> 00:08:02,900
točka sta enaka.

184
00:08:02,900 --> 00:08:05,030
Če smo bili videti
za 17, bi to imelo

185
00:08:05,030 --> 00:08:08,870
že v matriki, in začetno točko
in končna točka tega zadnjega ponovitvi

186
00:08:08,870 --> 00:08:11,820
preden prečka te točke,
mi pa bi našel 17 tam.

187
00:08:11,820 --> 00:08:15,510
To je samo takrat, ko so prečkali, da smo lahko
zagotavljajo, da je element ne

188
00:08:15,510 --> 00:08:17,180
obstajajo v matriki.

189
00:08:17,180 --> 00:08:20,260
>> Dajmo torej veliko manj
korakov od linearnega iskanja.

190
00:08:20,260 --> 00:08:23,250
V najslabšem primeru, smo imeli
razdeliti seznam n elementov

191
00:08:23,250 --> 00:08:27,770
Večkrat na pol, da bi našli cilja,
bodisi zato, ker je ciljna element

192
00:08:27,770 --> 00:08:33,110
bo nekje v zadnji
delitev, ali pa ne obstaja sploh.

193
00:08:33,110 --> 00:08:37,830
Torej, v najslabšem primeru pa moramo
split up array-- veš?

194
00:08:37,830 --> 00:08:40,510
Log n-krat; smo
morali zmanjšati problem

195
00:08:40,510 --> 00:08:42,610
pol določeno število ponovitev.

196
00:08:42,610 --> 00:08:45,160
Da kolikokrat je log n.

197
00:08:45,160 --> 00:08:46,510
>> Kaj je najboljši scenarij?

198
00:08:46,510 --> 00:08:48,899
No, prvič smo
izračunati srednjo vrednost,

199
00:08:48,899 --> 00:08:50,190
smo ugotovili, kaj iščemo.

200
00:08:50,190 --> 00:08:52,150
V vseh prejšnja
Primeri na binarnem iskanju

201
00:08:52,150 --> 00:08:55,489
smo pravkar šla čez, če bi imeli
iskal elementa 15,

202
00:08:55,489 --> 00:08:57,030
smo ugotovili, da bi takoj.

203
00:08:57,030 --> 00:08:58,321
To je bilo na samem začetku.

204
00:08:58,321 --> 00:09:01,200
To je bil razpolovišča
prvi poskus na razcepu

205
00:09:01,200 --> 00:09:03,950
o delitvi v binarnem iskanju.

206
00:09:03,950 --> 00:09:06,350
>> In tako v najslabšem
primera, binarno iskanje teče

207
00:09:06,350 --> 00:09:11,580
v log n, kar je bistveno bolje
kot linearno iskanje, v najslabšem primeru.

208
00:09:11,580 --> 00:09:16,210
V najboljšem primeru binarno
Iskanje teče v omega 1.

209
00:09:16,210 --> 00:09:18,990
Torej, binarno iskanje je veliko
bolje kot linearni iskanja,

210
00:09:18,990 --> 00:09:23,270
vendar boste morali spopasti s procesom
sortiranje svojo paleto, preden lahko

211
00:09:23,270 --> 00:09:26,140
vplivale na moč binarnega iskanja.

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

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

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