1
00:00:00,000 --> 00:00:03,346
>> [Glazbom]

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

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

4
00:00:06,220 --> 00:00:08,140
Dakle, binarna traži je
algoritam možemo koristiti

5
00:00:08,140 --> 00:00:10,530
pronaći element unutar niza.

6
00:00:10,530 --> 00:00:14,710
Za razliku od linearnog potrazi, to zahtijeva
poseban uvjet biti ispunjen prije,

7
00:00:14,710 --> 00:00:19,020
ali to je tako mnogo učinkovitiji ako
taj uvjet je, u stvari, susreo.

8
00:00:19,020 --> 00:00:20,470
>> Dakle, ono što je ideja ovog mjesta?

9
00:00:20,470 --> 00:00:21,780
to podijeli pa vladaj.

10
00:00:21,780 --> 00:00:25,100
Želimo smanjiti veličinu
potraga područje od pola svaki put

11
00:00:25,100 --> 00:00:27,240
kako bi se pronašli ciljani broj.

12
00:00:27,240 --> 00:00:29,520
Ovo je mjesto gdje se taj uvjet
dolazi u igru, iako.

13
00:00:29,520 --> 00:00:32,740
Možemo samo utjecati na snagu
eliminira polovice elemenata

14
00:00:32,740 --> 00:00:36,070
čak i bez gledanja na
ih, ako je niz sortira.

15
00:00:36,070 --> 00:00:39,200
>> Ako je kompletna mješavina gore,
Ne možemo samo iz ruke

16
00:00:39,200 --> 00:00:42,870
odbaciti polovina elemenata, jer
ne znamo što ćemo odbacivanje.

17
00:00:42,870 --> 00:00:45,624
No, ako je niz sortira,
možemo to učiniti, jer mi

18
00:00:45,624 --> 00:00:48,040
znam da je sve do
ostavi gdje smo trenutno

19
00:00:48,040 --> 00:00:50,500
mora biti manji od
Vrijednost smo trenutno.

20
00:00:50,500 --> 00:00:52,300
I sve do
Pravo gdje smo

21
00:00:52,300 --> 00:00:55,040
mora biti veći od vrijednosti
trenutno gledamo u.

22
00:00:55,040 --> 00:00:58,710
>> Zato što je pseudokod
koraci za binarnog pretraživanja?

23
00:00:58,710 --> 00:01:02,310
Mi ponovite ovaj postupak dok
polje ili, kao što smo nastavili kroz,

24
00:01:02,310 --> 00:01:07,740
sub polja, manjih komada
izvorni niz, od veličine 0.

25
00:01:07,740 --> 00:01:10,960
Izračunajte polovište
tekuće sub polja.

26
00:01:10,960 --> 00:01:14,460
>> Ako je vrijednost koju tražite
u tom elementu niza, zaustaviti.

27
00:01:14,460 --> 00:01:15,030
Pronašao si.

28
00:01:15,030 --> 00:01:16,550
To je odlično.

29
00:01:16,550 --> 00:01:19,610
Inače, ako je ciljani
manje od onoga što je u sredini,

30
00:01:19,610 --> 00:01:23,430
pa ako vrijednost tražimo
je niži od onoga što smo vidjeli,

31
00:01:23,430 --> 00:01:26,780
ponovite ovaj postupak opet, ali
promijeniti završne točke, umjesto

32
00:01:26,780 --> 00:01:29,300
da su izvorni
dovršiti cijeli niz,

33
00:01:29,300 --> 00:01:34,110
da se samo na lijevo
gdje smo samo pogledao.

34
00:01:34,110 --> 00:01:38,940
>> Znali smo da je srednji bila previsoka,
ili je meta bio manji od sredine,

35
00:01:38,940 --> 00:01:42,210
pa mora postojati, ako je to
uopće postoji u nizu,

36
00:01:42,210 --> 00:01:44,660
negdje lijevo od sredine.

37
00:01:44,660 --> 00:01:48,120
I tako ćemo postaviti niz
Položaj samo na lijevo

38
00:01:48,120 --> 00:01:51,145
od sredine kao novi krajnje točke.

39
00:01:51,145 --> 00:01:53,770
Suprotno tome, ako je ciljani
veća nego što je u sredini,

40
00:01:53,770 --> 00:01:55,750
mi je isti
proces, ali umjesto toga smo

41
00:01:55,750 --> 00:01:59,520
promijenite početnu točku se
samo desno od sredine

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

43
00:02:00,680 --> 00:02:03,220
A onda, ponovno smo započeli proces.

44
00:02:03,220 --> 00:02:05,220
>> Idemo vizualizirati to, u redu?

45
00:02:05,220 --> 00:02:08,620
Dakle, postoji mnogo događa i ovdje,
ali ovdje je niz od 15 elemenata.

46
00:02:08,620 --> 00:02:11,400
I mi ćemo biti praćenja
od puno više stvari ovaj put.

47
00:02:11,400 --> 00:02:13,870
Tako je u linearno pretraživanje, bili smo
Samo brige o cilju.

48
00:02:13,870 --> 00:02:15,869
No, ovaj put želimo
stalo gdje smo

49
00:02:15,869 --> 00:02:18,480
počinje izgledati, gdje
se zaustavljamo u potrazi,

50
00:02:18,480 --> 00:02:21,876
i što je srednji
tekuće polja.

51
00:02:21,876 --> 00:02:23,250
Dakle, ovdje mi ići s binarnim pretraživanja.

52
00:02:23,250 --> 00:02:25,290
Mi smo prilično mnogo dobar to ići, zar ne?

53
00:02:25,290 --> 00:02:28,650
Samo ću staviti dolje
ispod ovdje skup indeksa.

54
00:02:28,650 --> 00:02:32,430
To je u osnovi samo ono što je element
od niza govorimo o tome.

55
00:02:32,430 --> 00:02:34,500
S linearno pretraživanje, mi
briga, budući da mi

56
00:02:34,500 --> 00:02:36,800
trebaju znati koliko
Elementi smo Ponavljanje iznad,

57
00:02:36,800 --> 00:02:40,010
ali mi zapravo ne zanima me što
Element se trenutno gleda.

58
00:02:40,010 --> 00:02:41,014
U binarnom pretraživanje, činimo.

59
00:02:41,014 --> 00:02:42,930
I tako oni su samo
postoji kao mali vodič.

60
00:02:42,930 --> 00:02:44,910
>> Tako možemo početi, zar ne?

61
00:02:44,910 --> 00:02:46,240
Pa, ne baš.

62
00:02:46,240 --> 00:02:48,160
Sjeti se što sam rekao
o binarnom pretraživanje?

63
00:02:48,160 --> 00:02:50,955
Ne možemo to učiniti na
nesortirani niz inače,

64
00:02:50,955 --> 00:02:55,820
mi ne jamči da je
određeni elementi ili vrijednosti nisu

65
00:02:55,820 --> 00:02:57,650
nehotično
odbačena kada smo jednostavno

66
00:02:57,650 --> 00:02:59,920
odlučili ignorirati polovice polja.

67
00:02:59,920 --> 00:03:02,574
>> Tako jedan korak s binarnim pretraživanje
je morate imati sortiran niz.

68
00:03:02,574 --> 00:03:05,240
A možete koristiti bilo koji od sortiranjem
Algoritmi Razgovarali smo o

69
00:03:05,240 --> 00:03:06,700
da bi vas na to mjesto.

70
00:03:06,700 --> 00:03:10,370
Tako sada, mi smo u poziciji gdje
možemo izvesti binarni pretragu.

71
00:03:10,370 --> 00:03:12,560
>> Tako ćemo ponoviti postupak
korak po korak i držati

72
00:03:12,560 --> 00:03:14,830
pratiti što se događa, kao idemo.

73
00:03:14,830 --> 00:03:17,980
Dakle, prvo što trebate učiniti je izračunati
polovište trenutnog polja.

74
00:03:17,980 --> 00:03:20,620
Pa, mi ćemo reći da smo, prije
svega, u potrazi za vrijednost 19.

75
00:03:20,620 --> 00:03:22,290
Pokušavamo naći broj 19.

76
00:03:22,290 --> 00:03:25,380
Prvi element ove
Niz se nalazi na indeks nula,

77
00:03:25,380 --> 00:03:28,880
i posljednji element ovog
Niz se nalazi na indeks 14.

78
00:03:28,880 --> 00:03:31,430
I tako ćemo nazvati one početak i kraj.

79
00:03:31,430 --> 00:03:35,387
>> Tako smo izračunati polovište po
dodajući 0 plus 14 podijeljeno s 2;

80
00:03:35,387 --> 00:03:36,720
prilično jednostavan srednji.

81
00:03:36,720 --> 00:03:40,190
I možemo reći da je
sredina je sada 7.

82
00:03:40,190 --> 00:03:43,370
Tako je 15 ono što tražite?

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

84
00:03:43,940 --> 00:03:45,270
Tražimo 19.

85
00:03:45,270 --> 00:03:49,400
Ali mi znamo da je 19 veći
od onoga što smo pronašli u sredini.

86
00:03:49,400 --> 00:03:52,470
>> Dakle, ono što možemo učiniti je
promijeniti početnu točku

87
00:03:52,470 --> 00:03:57,280
da se samo s desne strane
srednji, i opet ponovite postupak.

88
00:03:57,280 --> 00:04:01,690
A kad smo to, mi sada reći
Novi početak točka je niz lokacija 8.

89
00:04:01,690 --> 00:04:07,220
Ono što smo učinili je uspješno smo
ignorirao je sve na lijevoj strani 15.

90
00:04:07,220 --> 00:04:09,570
Mi smo eliminirani pola
problema, a sada,

91
00:04:09,570 --> 00:04:13,510
umjesto da se traži
više od 15 elemenata u našoj polja,

92
00:04:13,510 --> 00:04:15,610
imamo samo tražiti više od 7.

93
00:04:15,610 --> 00:04:17,706
Dakle 8 je nova polazna točka.

94
00:04:17,706 --> 00:04:19,600
14 je i dalje krajnje točke.

95
00:04:19,600 --> 00:04:21,430
>> A sada, idemo preko toga opet.

96
00:04:21,430 --> 00:04:22,810
Mi izračunati novu središnju točku.

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

98
00:04:27,130 --> 00:04:28,660
Je li to ono što tražite?

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

100
00:04:30,110 --> 00:04:32,930
Mi smo u potrazi za vrijednost koja je
manje od onoga što smo upravo otkrili.

101
00:04:32,930 --> 00:04:34,721
Tako ćemo ponoviti
opet proces.

102
00:04:34,721 --> 00:04:38,280
Idemo promijeniti završne točke do
biti samo na lijevo od sredine.

103
00:04:38,280 --> 00:04:41,800
Tako je nova završna točka postaje 10.

104
00:04:41,800 --> 00:04:44,780
A sada, to je jedini dio
Niz moramo sortirati kroz.

105
00:04:44,780 --> 00:04:48,460
Dakle, sada smo eliminirani
12 od 15 elemenata.

106
00:04:48,460 --> 00:04:51,550
Znamo da ako 19
postoji u nizu, to

107
00:04:51,550 --> 00:04:57,210
mora postojati negdje između elementa
broj 8 i broj 10 elementa.

108
00:04:57,210 --> 00:04:59,400
>> Tako smo ponovno izračunati novu središnju točku.

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

110
00:05:02,900 --> 00:05:05,074
I u ovom slučaju, izgledaju,
Cilj je na sredini.

111
00:05:05,074 --> 00:05:06,740
Pronašli smo upravo ono što smo tražili.

112
00:05:06,740 --> 00:05:07,780
Možemo zaustaviti.

113
00:05:07,780 --> 00:05:10,561
Uspješno završeno
binarni pretraživanja.

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

115
00:05:11,060 --> 00:05:13,930
Tako znamo ovaj algoritam
radi ako je meta

116
00:05:13,930 --> 00:05:16,070
negdje unutar polja.

117
00:05:16,070 --> 00:05:19,060
Je li ovaj algoritam raditi ako
meta nije u nizu?

118
00:05:19,060 --> 00:05:20,810
Pa, neka je to početak
opet, i ovaj put,

119
00:05:20,810 --> 00:05:23,380
pogledajmo za element
16, koji se vizualno možemo vidjeti

120
00:05:23,380 --> 00:05:25,620
ne postoji nigdje u nizu.

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

122
00:05:27,110 --> 00:05:28,590
Krajnja točka je opet 14.

123
00:05:28,590 --> 00:05:32,490
Oni su indeksi prvi i
Posljednji elementi kompletnog niza.

124
00:05:32,490 --> 00:05:36,057
A mi ćemo proći kroz proces samo smo
opet išli putem, pokušava pronaći 16,

125
00:05:36,057 --> 00:05:39,140
iako vizualno, već možemo
reći da to neće biti tamo.

126
00:05:39,140 --> 00:05:43,450
Mi samo želite biti sigurni da taj algoritam
će, u stvari, i dalje raditi na neki način

127
00:05:43,450 --> 00:05:46,310
a ne samo nas ostaviti
zaglavi u beskonačnu petlju.

128
00:05:46,310 --> 00:05:48,190
>> Dakle, što je korak prvi?

129
00:05:48,190 --> 00:05:50,230
Izračunajte polovište
tekuće polja.

130
00:05:50,230 --> 00:05:52,790
Što je srednji
trenutnog niza?

131
00:05:52,790 --> 00:05:54,410
Pa, to je 7, zar ne?

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

133
00:05:57,560 --> 00:05:59,280
Je li 15 ono što tražite?

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

135
00:05:59,780 --> 00:06:02,930
To je prilično blizu, ali mi smo u potrazi
za vrijednosti nešto veće od toga.

136
00:06:02,930 --> 00:06:06,310
>> Dakle, znamo da će to
biti nigdje na lijevoj strani 15.

137
00:06:06,310 --> 00:06:08,540
Cilj je veća od
što je u središnjoj točki.

138
00:06:08,540 --> 00:06:12,450
I tako smo postavili novu početnu točku
biti samo na desnoj sredini.

139
00:06:12,450 --> 00:06:16,130
Središnja točka je trenutno 7, tako
recimo nova polazna točka je 8.

140
00:06:16,130 --> 00:06:18,130
A ono što smo uspješno
učinio ponovno se ignorira

141
00:06:18,130 --> 00:06:21,150
cijela lijeva polovica polja.

142
00:06:21,150 --> 00:06:23,750
>> Sada ćemo ponoviti
proces još jednom.

143
00:06:23,750 --> 00:06:24,910
Izračunajte novu središnju točku.

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

145
00:06:29,350 --> 00:06:31,060
Je li 23 ono što tražite?

146
00:06:31,060 --> 00:06:31,870
Nažalost ne.

147
00:06:31,870 --> 00:06:34,930
Mi smo u potrazi za vrijednošću
koji je manji od 23.

148
00:06:34,930 --> 00:06:37,850
I tako, u ovom slučaju, idemo
za promjenu završne točke da se samo

149
00:06:37,850 --> 00:06:40,035
lijevo tekuće sredine.

150
00:06:40,035 --> 00:06:43,440
Trenutni srednji je 11, a
pa ćemo postaviti novu završnu točku

151
00:06:43,440 --> 00:06:46,980
za sljedeći put idemo
kroz ovaj proces do 10.

152
00:06:46,980 --> 00:06:48,660
>> Opet ćemo proći kroz proces ponovno.

153
00:06:48,660 --> 00:06:49,640
Izračunajte polovište.

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

155
00:06:53,100 --> 00:06:54,750
Je li 19 ono što tražite?

156
00:06:54,750 --> 00:06:55,500
Nažalost ne.

157
00:06:55,500 --> 00:06:58,050
Još uvijek u potrazi za
broj manje od toga.

158
00:06:58,050 --> 00:07:02,060
Tako ćemo promijeniti završne točke ovog puta
biti samo lijevo od sredine.

159
00:07:02,060 --> 00:07:05,532
Središnja točka je trenutno 9,
tako da je krajnja točka će biti 8.

160
00:07:05,532 --> 00:07:07,920
I sada, mi samo tražimo
na jedan element niza.

161
00:07:07,920 --> 00:07:10,250
>> Što je srednji ovog niza?

162
00:07:10,250 --> 00:07:13,459
Pa, ona počinje u 8, što
završava u 8, sredina je 8.

163
00:07:13,459 --> 00:07:14,750
Je li to ono što tražite?

164
00:07:14,750 --> 00:07:16,339
Jesmo li u potrazi za 17?

165
00:07:16,339 --> 00:07:17,380
Ne, mi smo u potrazi za 16 godina.

166
00:07:17,380 --> 00:07:20,160
Dakle, ako postoji u nizu,
mora postojati negdje

167
00:07:20,160 --> 00:07:21,935
s lijeve strane, gdje smo trenutno.

168
00:07:21,935 --> 00:07:23,060
Pa što ćemo učiniti?

169
00:07:23,060 --> 00:07:26,610
Pa, mi ćemo postaviti završne točke da se samo
lijevo tekuće sredine.

170
00:07:26,610 --> 00:07:29,055
Tako ćemo mijenjati završne točke do 7.

171
00:07:29,055 --> 00:07:32,120
Vidite li što se upravo
dogodilo ovdje, iako?

172
00:07:32,120 --> 00:07:33,370
Potražite ovdje.

173
00:07:33,370 --> 00:07:35,970
>> Početak je sada veći od kraja.

174
00:07:35,970 --> 00:07:39,620
Efektivno, dva kraja
našeg polja su prešli,

175
00:07:39,620 --> 00:07:42,252
a početna točka je
Sada nakon krajnje točke.

176
00:07:42,252 --> 00:07:43,960
Pa, da ne
nikakvog smisla, zar ne?

177
00:07:43,960 --> 00:07:47,960
Tako sada, što možemo reći je da
imaju pod niz veličina 0.

178
00:07:47,960 --> 00:07:50,110
I jednom smo dobivši
ovom trenutku, sada možemo

179
00:07:50,110 --> 00:07:53,940
jamčiti da element 16
ne postoji u nizu,

180
00:07:53,940 --> 00:07:56,280
jer početne točke
i krajnje točke su prešli.

181
00:07:56,280 --> 00:07:58,340
I tako to ne postoji.

182
00:07:58,340 --> 00:08:01,340
Sada primijetite da je to nešto
razlikuje od početne točke i na kraju

183
00:08:01,340 --> 00:08:02,900
ukazati se isto.

184
00:08:02,900 --> 00:08:05,030
Ako smo bili u potrazi
za 17, to bi

185
00:08:05,030 --> 00:08:08,870
je u nizu, a početne točke
i završna točka tog zadnjeg iteracije

186
00:08:08,870 --> 00:08:11,820
Prije te točke prešli,
bismo našli 17 tamo.

187
00:08:11,820 --> 00:08:15,510
To je samo kad oni prelaze da možemo
jamčiti da se element ne

188
00:08:15,510 --> 00:08:17,180
postoje u nizu.

189
00:08:17,180 --> 00:08:20,260
>> Tako ćemo se puno manje
koraka od linearnog pretraživanje.

190
00:08:20,260 --> 00:08:23,250
U najgorem slučaju, imali smo
podijeliti popis n elemenata

191
00:08:23,250 --> 00:08:27,770
više puta na pola kako bi pronašli metu,
bilo zato što je ciljani element koji

192
00:08:27,770 --> 00:08:33,110
će biti negdje u posljednja
podjela, ili to ne postoji.

193
00:08:33,110 --> 00:08:37,830
Dakle, u najgorem slučaju, moramo
razišli su array-- znaš?

194
00:08:37,830 --> 00:08:40,510
Prijava od n puta; mi
morati smanjiti problem

195
00:08:40,510 --> 00:08:42,610
pola određeni broj puta.

196
00:08:42,610 --> 00:08:45,160
Taj broj puta je log n.

197
00:08:45,160 --> 00:08:46,510
>> Koji je najbolji mogući scenarij?

198
00:08:46,510 --> 00:08:48,899
Pa, prvi put smo
izračunati polovište,

199
00:08:48,899 --> 00:08:50,190
možemo pronaći ono što tražite.

200
00:08:50,190 --> 00:08:52,150
U sva prethodna
primjeri na binarnom pretraživanje

201
00:08:52,150 --> 00:08:55,489
smo samo otišli preko, ako smo imali
u potrazi za element 15,

202
00:08:55,489 --> 00:08:57,030
bismo otkrili da je odmah.

203
00:08:57,030 --> 00:08:58,321
To je na samom početku.

204
00:08:58,321 --> 00:09:01,200
To je polovište
prvi pokušaj u Splitu

205
00:09:01,200 --> 00:09:03,950
od podjele u binarnom pretraživanja.

206
00:09:03,950 --> 00:09:06,350
>> I tako je u najgore
slučaj, binarno traženje traje

207
00:09:06,350 --> 00:09:11,580
u log N, koji je znatno bolja
nego linearno pretraživanje, u najgorem slučaju.

208
00:09:11,580 --> 00:09:16,210
U najboljem slučaju, binarni
traži radi omega od 1.

209
00:09:16,210 --> 00:09:18,990
Dakle, binarna traži puno
bolji od linearnog pretraživanje,

210
00:09:18,990 --> 00:09:23,270
ali morate se nositi s procesom
sortiranje svoj niz prije nego što možete

211
00:09:23,270 --> 00:09:26,140
iskoristiti snagu binarnog pretraživanja.

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

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

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