1
00:00:00,000 --> 00:00:03,346
>> [Muzikos grojimo]

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

3
00:00:05,258 --> 00:00:06,220
>> Doug LLOYD: Visos dešinę.

4
00:00:06,220 --> 00:00:08,140
Taigi dvejetainis paieškos yra
algoritmas mes galime naudoti

5
00:00:08,140 --> 00:00:10,530
rasti elementą viduje masyvą.

6
00:00:10,530 --> 00:00:14,710
Skirtingai nuo linijiniu paieškoje, ji reikalauja
ypatingo būti laikomasi iš anksto,

7
00:00:14,710 --> 00:00:19,020
bet tai tiek daug efektyvesnis, jei
kad sąlyga yra, iš tikrųjų, met.

8
00:00:19,020 --> 00:00:20,470
>> Taigi, kas yra idėja čia?

9
00:00:20,470 --> 00:00:21,780
tai skaldyk ir valdyk.

10
00:00:21,780 --> 00:00:25,100
Mes norime sumažinti dydį
paieška plotas perpus kiekvieną kartą

11
00:00:25,100 --> 00:00:27,240
tam, kad rasti tikslinę, skaičių.

12
00:00:27,240 --> 00:00:29,520
Tai kur ta sąlyga
ateina į žaidimą, nors.

13
00:00:29,520 --> 00:00:32,740
Mes galime tik sverto galia
pašalinant pusė elementų

14
00:00:32,740 --> 00:00:36,070
net žiūri
juos, jei masyvas surūšiuotas.

15
00:00:36,070 --> 00:00:39,200
>> Jei tai pilnas išmaišyti,
mes galime ne tik iš rankų

16
00:00:39,200 --> 00:00:42,870
išmesti pusė elementų, nes
mes nežinome, ką mes dėžę.

17
00:00:42,870 --> 00:00:45,624
Bet jei masyvas surūšiuotas,
mes galime padaryti, nes mes

18
00:00:45,624 --> 00:00:48,040
žinau, kad viskas su tuo,
į kairę, kur šiuo metu yra

19
00:00:48,040 --> 00:00:50,500
turi būti mažesnis nei
vertė mes šiuo metu.

20
00:00:50,500 --> 00:00:52,300
Ir viskas į
teisė, kur mes esame

21
00:00:52,300 --> 00:00:55,040
turi būti didesnis, negu vertė
mes šiuo metu ieško.

22
00:00:55,040 --> 00:00:58,710
>> Taigi, kas yra Pseudocode
žingsniai dvejetainis ieškoti?

23
00:00:58,710 --> 00:01:02,310
Mes pakartokite šį procesą tol, kol
masyvas arba, kaip mes pereiti per,

24
00:01:02,310 --> 00:01:07,740
sub matricos, mažesni gabalai
originalus masyvas, yra dydis 0.

25
00:01:07,740 --> 00:01:10,960
Apskaičiuokite Mediana
dabartinės pietus masyvo.

26
00:01:10,960 --> 00:01:14,460
>> Jei reikšmė jūs ieškote yra
toje masyvo elemento, sustabdyti.

27
00:01:14,460 --> 00:01:15,030
Jūs ją radau.

28
00:01:15,030 --> 00:01:16,550
Tai puiku.

29
00:01:16,550 --> 00:01:19,610
Priešingu atveju, jei tikslas yra
mažiau nei tai, kas yra viduryje,

30
00:01:19,610 --> 00:01:23,430
Taigi, jei vertės mes ieškome
už yra mažesnis nei matome,

31
00:01:23,430 --> 00:01:26,780
vėl pakartokite šį procesą, bet
pakeisti pabaigos tašką, vietoj to,

32
00:01:26,780 --> 00:01:29,300
buvimo originalus
užpildyti visą masyvą,

33
00:01:29,300 --> 00:01:34,110
būti tik į kairę
kur mes tiesiog atrodė.

34
00:01:34,110 --> 00:01:38,940
>> Mes žinojome, kad vidurinioji buvo per didelis,
arba tikslinis buvo mažesnis nei viduryje,

35
00:01:38,940 --> 00:01:42,210
ir todėl ji turi egzistuoti, jei ji
egzistuoja ne visi masyvo,

36
00:01:42,210 --> 00:01:44,660
kur nors į centrą kairę.

37
00:01:44,660 --> 00:01:48,120
Ir todėl mes nustatyti masyvo
vietą tiesiog į kairę

38
00:01:48,120 --> 00:01:51,145
iš vidurio taško, kaip naujos galinio taško.

39
00:01:51,145 --> 00:01:53,770
Priešingai, jei tikslas yra
didesnis nei tai, kas yra viduryje,

40
00:01:53,770 --> 00:01:55,750
mes darome tą patį
procesas, tačiau vietoj to mes

41
00:01:55,750 --> 00:01:59,520
pakeisti pradinį tašką, kad būtų
tiesiog į centrą dešinėje

42
00:01:59,520 --> 00:02:00,680
mes tiesiog apskaičiuotas.

43
00:02:00,680 --> 00:02:03,220
Ir tada mes pradėti procesą dar kartą.

44
00:02:03,220 --> 00:02:05,220
>> Leiskite vizualizuoti tai, gerai?

45
00:02:05,220 --> 00:02:08,620
Taigi ten daug vyksta ir čia
bet čia AN 15 elementų masyvas.

46
00:02:08,620 --> 00:02:11,400
Ir mes ketiname būti sekti
iš daug daugiau dalykų šiuo metu.

47
00:02:11,400 --> 00:02:13,870
Taigi tiesinės paieškos, mes buvome
tik rūpinasi į taikinį.

48
00:02:13,870 --> 00:02:15,869
Bet šį kartą mes norime
rūpi, kur mes esame

49
00:02:15,869 --> 00:02:18,480
pradeda atrodyti, kur
mes sustoti ieško,

50
00:02:18,480 --> 00:02:21,876
ir kas Mediana
dabartinės masyvo.

51
00:02:21,876 --> 00:02:23,250
Taigi čia mes einame su dvejetainiu paiešką.

52
00:02:23,250 --> 00:02:25,290
Mes gana daug gera eiti, tiesa?

53
00:02:25,290 --> 00:02:28,650
Aš tik ketina pribaigti
Toliau Čia indeksų rinkinys.

54
00:02:28,650 --> 00:02:32,430
Tai iš esmės yra tai, ką elementas
masyvo mes kalbame apie.

55
00:02:32,430 --> 00:02:34,500
Su linijiniu paieškoje, mes
rūpintis, nes mes

56
00:02:34,500 --> 00:02:36,800
reikia žinoti, kiek
elementai mes Iteracja per,

57
00:02:36,800 --> 00:02:40,010
bet mes ne iš tikrųjų rūpi, ką
elementas mes šiuo metu ieško.

58
00:02:40,010 --> 00:02:41,014
Be dvejetainis paieškos, mes darome.

59
00:02:41,014 --> 00:02:42,930
Ir taip jie yra tik
ten taip mažai vadove.

60
00:02:42,930 --> 00:02:44,910
>> Taigi, mes galime pradėti, tiesa?

61
00:02:44,910 --> 00:02:46,240
Na, ne visai.

62
00:02:46,240 --> 00:02:48,160
Prisiminkite, ką aš sakiau
apie dvejetainis paieškos?

63
00:02:48,160 --> 00:02:50,955
Mes negalime daryti ant
nerūšiuotų masyvas ar kitur,

64
00:02:50,955 --> 00:02:55,820
mes ne užtikrinti, kad
tam tikri elementai ar vertybės nėra

65
00:02:55,820 --> 00:02:57,650
netyčinio
išmesti, kai mes tiesiog

66
00:02:57,650 --> 00:02:59,920
nuspręsti ignoruoti pusė masyvo.

67
00:02:59,920 --> 00:03:02,574
>> Taigi vienas žingsnis, su dvejetainiu paieškos
yra, jūs turite turėti surūšiuoti masyvo.

68
00:03:02,574 --> 00:03:05,240
Ir jūs galite naudoti bet į rūšiavimo
algoritmai mes kalbėjome apie

69
00:03:05,240 --> 00:03:06,700
kad jums į tą padėtį.

70
00:03:06,700 --> 00:03:10,370
Taigi dabar mes tokioje padėtyje, kai
mes galime atlikti dvejetainis paiešką.

71
00:03:10,370 --> 00:03:12,560
>> Taigi leiskite pakartoti procesą
žingsnis po žingsnio ir išlaikyti

72
00:03:12,560 --> 00:03:14,830
stebėti, kas vyksta, kaip mes einame.

73
00:03:14,830 --> 00:03:17,980
Taigi pirmiausia turime padaryti, tai apskaičiuoti
dabartinio masyvo viduryje.

74
00:03:17,980 --> 00:03:20,620
Na, mes pasakyti mes, pirmiausia
gale, ieško vertės 19.

75
00:03:20,620 --> 00:03:22,290
Mes bandome rasti skaičių 19.

76
00:03:22,290 --> 00:03:25,380
Pirmasis elementas šis
masyvas yra nulinės indeksą,

77
00:03:25,380 --> 00:03:28,880
ir paskutinis elementas tai
masyvas yra įsikūręs 14 indeksą.

78
00:03:28,880 --> 00:03:31,430
Ir taip mes vadiname tuos pradžios ir pabaigos.

79
00:03:31,430 --> 00:03:35,387
>> Taigi mes galime apskaičiuoti pagal viduriu
pridėti 0 plius 14, padalinta iš 2;

80
00:03:35,387 --> 00:03:36,720
gana paprasta viduryje.

81
00:03:36,720 --> 00:03:40,190
Ir mes galime pasakyti, kad
Mediana dabar 7.

82
00:03:40,190 --> 00:03:43,370
Taigi yra 15, kas mes ieškome?

83
00:03:43,370 --> 00:03:43,940
Ne, tai nėra.

84
00:03:43,940 --> 00:03:45,270
Mes ieškome 19.

85
00:03:45,270 --> 00:03:49,400
Bet mes žinome, kad 19 yra didesnis
nei tai, ką mes radome viduryje.

86
00:03:49,400 --> 00:03:52,470
>> Taigi, ką mes galime padaryti, tai
pakeisti pradinį tašką

87
00:03:52,470 --> 00:03:57,280
būti tik į dešinę
viduryje, ir vėl pakartokite šį procesą.

88
00:03:57,280 --> 00:04:01,690
Ir kai mes tai padarysime, mes dabar pasakyti
nauja pradžia taškas yra masyvas vietą 8.

89
00:04:01,690 --> 00:04:07,220
Ką mes iš tikrųjų padaryta yra
ignoruojami viskas 15 kairę.

90
00:04:07,220 --> 00:04:09,570
Mes pašalintas pusę
Problemos, ir dabar,

91
00:04:09,570 --> 00:04:13,510
vietoj to, kad ieškoti
daugiau nei 15 elementai mūsų masyvas,

92
00:04:13,510 --> 00:04:15,610
mes tik turite ieškoti per 7.

93
00:04:15,610 --> 00:04:17,706
Taigi 8 yra naujas pradžios taškas.

94
00:04:17,706 --> 00:04:19,600
14 vis dar yra galutinis taškas.

95
00:04:19,600 --> 00:04:21,430
>> Ir dabar, mes einame per šį kartą.

96
00:04:21,430 --> 00:04:22,810
Mes apskaičiuoti naują taško.

97
00:04:22,810 --> 00:04:27,130
8 plius 14 yra 22, padalytą iš 2 11.

98
00:04:27,130 --> 00:04:28,660
Ar tai, ką mes ieškome?

99
00:04:28,660 --> 00:04:30,110
Ne, tai nėra.

100
00:04:30,110 --> 00:04:32,930
Mes ieškome vertė ŠTAI
mažiau nei tai, ką mes ką tik sužinojau.

101
00:04:32,930 --> 00:04:34,721
Taigi mes ketiname pakartoti
vėl procesas.

102
00:04:34,721 --> 00:04:38,280
Mes ketiname pakeisti į pabaigos tašką
būti tik į centrą kairę.

103
00:04:38,280 --> 00:04:41,800
Taigi naujasis galutinis taškas tampa 10.

104
00:04:41,800 --> 00:04:44,780
O dabar, tai tik dalis
masyvas turime sutvarkyti.

105
00:04:44,780 --> 00:04:48,460
Taigi, mes jau pašalintas
12 iš 15 elementų.

106
00:04:48,460 --> 00:04:51,550
Mes žinome, kad jei 19
egzistuoja masyvo, ją

107
00:04:51,550 --> 00:04:57,210
turi egzistuoti kažkur tarp elemento
numeris 8 ir elementas numeris 10.

108
00:04:57,210 --> 00:04:59,400
>> Taigi, mes vėl skaičiuoja naujų taško.

109
00:04:59,400 --> 00:05:02,900
8 plius 10 yra 18, padalytą iš 2 9.

110
00:05:02,900 --> 00:05:05,074
Ir šiuo atveju, atrodo, The
tikslas yra viduryje.

111
00:05:05,074 --> 00:05:06,740
Mes nustatėme, ką mes ieškome.

112
00:05:06,740 --> 00:05:07,780
Mes galime sustabdyti.

113
00:05:07,780 --> 00:05:10,561
Mes sėkmingai
dvejetainis paieškos.

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

115
00:05:11,060 --> 00:05:13,930
Taigi mes žinome, šį algoritmą
veikia, jei tikslas yra

116
00:05:13,930 --> 00:05:16,070
kažkur viduje masyvo.

117
00:05:16,070 --> 00:05:19,060
Ar šį algoritmą dirbti, jei
taikinys yra ne masyvo?

118
00:05:19,060 --> 00:05:20,810
Na, pradėkime ją
vėl, ir šį kartą,

119
00:05:20,810 --> 00:05:23,380
Pažvelkime už elementą
16, kuris vizualiai matome

120
00:05:23,380 --> 00:05:25,620
neegzistuoja niekur masyvo.

121
00:05:25,620 --> 00:05:27,110
>> Pradžios taškas yra vėl 0.

122
00:05:27,110 --> 00:05:28,590
Galutinis taškas vėl 14.

123
00:05:28,590 --> 00:05:32,490
Tai yra pirmosios indeksai ir
paskutiniai elementai visiškai masyvo.

124
00:05:32,490 --> 00:05:36,057
Ir mes eiti per šį procesą mes tiesiog
išgyveno vėl bando rasti 16,

125
00:05:36,057 --> 00:05:39,140
nors vizualiai, jau galime
pasakyti, kad ji nesiruošia būti ten.

126
00:05:39,140 --> 00:05:43,450
Mes tiesiog norite įsitikinti šį algoritmą
bus, iš tiesų, vis dar dirba tam tikru būdu

127
00:05:43,450 --> 00:05:46,310
o ne tiesiog palikite mums
įstrigo begalinis ciklas.

128
00:05:46,310 --> 00:05:48,190
>> Taigi, kas yra žingsnis pirmiausia?

129
00:05:48,190 --> 00:05:50,230
Apskaičiuokite Mediana
dabartinės masyvo.

130
00:05:50,230 --> 00:05:52,790
Kas yra pusiaukelė
dabartinės masyvo?

131
00:05:52,790 --> 00:05:54,410
Na, tai 7, tiesa?

132
00:05:54,410 --> 00:05:57,560
14 plius 0, padalytą iš 2 7.

133
00:05:57,560 --> 00:05:59,280
15, ką mes ieškome?

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

135
00:05:59,780 --> 00:06:02,930
Tai gana arti, bet mes ieškome
kurių vertė šiek tiek didesnis, nei nurodyta.

136
00:06:02,930 --> 00:06:06,310
>> Taigi mes žinome, kad jis ketina
būti kur 15 kairę.

137
00:06:06,310 --> 00:06:08,540
Taikinys yra didesnis nei
kas yra viduryje.

138
00:06:08,540 --> 00:06:12,450
Ir taip mes nustatome naują pradžios tašką į
būti tik į viduryje dešinėje.

139
00:06:12,450 --> 00:06:16,130
Mediana šiuo metu 7, todėl
tarkim naujas pradžios taškas yra 8.

140
00:06:16,130 --> 00:06:18,130
Ir ką mes iš tikrųjų
daroma vėl ignoruojamas

141
00:06:18,130 --> 00:06:21,150
visa kairėje pusėje, masyvo.

142
00:06:21,150 --> 00:06:23,750
>> Dabar mes pakartoti
apdoroti dar kartą.

143
00:06:23,750 --> 00:06:24,910
Apskaičiuokite naują taško.

144
00:06:24,910 --> 00:06:29,350
8 plius 14 yra 22, padalytą iš 2 11.

145
00:06:29,350 --> 00:06:31,060
Ar 23 ką mes ko ieškote?

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

147
00:06:31,870 --> 00:06:34,930
Mes ieškome vertė
kuris yra mažesnis nei 23.

148
00:06:34,930 --> 00:06:37,850
Ir taip, šiuo atveju, mes ketiname
pakeisti pabaigos tašką būti tik

149
00:06:37,850 --> 00:06:40,035
į dabartinės vidurio taško pusėje.

150
00:06:40,035 --> 00:06:43,440
Dabartinė Mediana yra 11, o
todėl mes nustatyti naują pabaigos tašką

151
00:06:43,440 --> 00:06:46,980
kitą kartą mes einame
per šį procesą iki 10.

152
00:06:46,980 --> 00:06:48,660
>> Vėlgi, mes einame per šį procesą dar kartą.

153
00:06:48,660 --> 00:06:49,640
Apskaičiuokite taško.

154
00:06:49,640 --> 00:06:53,100
8 plius 10, padalytą iš 2 9.

155
00:06:53,100 --> 00:06:54,750
Ar 19 ką mes ko ieškote?

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

157
00:06:55,500 --> 00:06:58,050
Mes vis dar ieškome
skaičius mažesnis nei.

158
00:06:58,050 --> 00:07:02,060
Taigi mes pakeisti šio galutinio taško šį kartą
būti tik į centrą kairę.

159
00:07:02,060 --> 00:07:05,532
Mediana šiuo metu 9,
todėl galutinis taškas bus 8.

160
00:07:05,532 --> 00:07:07,920
Ir dabar, mes tiesiog ieškote
bent vieną elementą masyvo.

161
00:07:07,920 --> 00:07:10,250
>> Kokia šio masyvo viduryje?

162
00:07:10,250 --> 00:07:13,459
Na, tai prasideda 8, tai
baigiasi 8, Mediana yra 8.

163
00:07:13,459 --> 00:07:14,750
Ar tai, ką mes ieškome?

164
00:07:14,750 --> 00:07:16,339
Ar mes ieškome 17?

165
00:07:16,339 --> 00:07:17,380
Ne, mes ieškome 16.

166
00:07:17,380 --> 00:07:20,160
Taigi, jei ji egzistuoja masyve,
ji turi egzistuoti kažkur

167
00:07:20,160 --> 00:07:21,935
į kur šiuo metu yra kairėje.

168
00:07:21,935 --> 00:07:23,060
Taigi, ką mes ketiname daryti?

169
00:07:23,060 --> 00:07:26,610
Na, mes nustatyti pabaigos tašką būti tik
į dabartinės vidurio taško pusėje.

170
00:07:26,610 --> 00:07:29,055
Taigi mes pakeisti galutinį tašką iki 7.

171
00:07:29,055 --> 00:07:32,120
Ar matote, ką tik
čia nutiko, nors?

172
00:07:32,120 --> 00:07:33,370
Pažiūrėkite čia dabar.

173
00:07:33,370 --> 00:07:35,970
>> Pradėti dabar didesnis nei pabaigos.

174
00:07:35,970 --> 00:07:39,620
Veiksmingi, du galai
Mūsų masyvo kirto,

175
00:07:39,620 --> 00:07:42,252
o pradžios taškas yra
dabar po šio galutinio taško.

176
00:07:42,252 --> 00:07:43,960
Na, tai nėra
jokios prasmės, tiesa?

177
00:07:43,960 --> 00:07:47,960
Taigi, dabar, ką mes galime pasakyti, mes
turi sub masyvas dydis 0.

178
00:07:47,960 --> 00:07:50,110
Ir kai mes Dotarłeś
Šiuo metu mes galime dabar

179
00:07:50,110 --> 00:07:53,940
užtikrinti, kad elementas 16
neegzistuoja masyvo,

180
00:07:53,940 --> 00:07:56,280
nes pradžios taško
ir galutinis taškas kirto.

181
00:07:56,280 --> 00:07:58,340
Ir todėl ten nėra.

182
00:07:58,340 --> 00:08:01,340
Dabar, pastebėti, kad tai yra šiek tiek
kitoks, nei pradžios tašką ir pabaigos

183
00:08:01,340 --> 00:08:02,900
taškas yra ta pati.

184
00:08:02,900 --> 00:08:05,030
Jei būtume gyvenę ieško
17, ji turėtų

185
00:08:05,030 --> 00:08:08,870
buvo masyvo ir pradžios taškas
ir galutinis taškas pastarojo iteracijos

186
00:08:08,870 --> 00:08:11,820
prieš kirto tie taškai,
mes nustatėme, 17 ten.

187
00:08:11,820 --> 00:08:15,510
Tai tik tada, kai jie kerta, kad mes galime
garantuoja, kad elementas, nėra

188
00:08:15,510 --> 00:08:17,180
egzistuoja masyvo.

189
00:08:17,180 --> 00:08:20,260
>> Taigi galime imtis daug mažiau
žingsniai kaip tiesinės paieškoje.

190
00:08:20,260 --> 00:08:23,250
Blogiausiu atveju, mes turėjome
padalinti iš n elementų sąrašą

191
00:08:23,250 --> 00:08:27,770
pakartotinai per pusę rasti tikslą,
arba todėl, kad tikslinė elementas

192
00:08:27,770 --> 00:08:33,110
bus kažkur paskutinis
skaidymą arba ji neegzistuoja ne visi.

193
00:08:33,110 --> 00:08:37,830
Taigi, blogiausiu atveju, mes turime
suskaidytas array-- jūs žinote?

194
00:08:37,830 --> 00:08:40,510
Prisijungti n kartų; mes
turi sumažinti problemą

195
00:08:40,510 --> 00:08:42,610
pusę tam tikrą skaičių kartų.

196
00:08:42,610 --> 00:08:45,160
Tai kiek kartų yra žurnalas n.

197
00:08:45,160 --> 00:08:46,510
>> Koks geriausias scenarijus?

198
00:08:46,510 --> 00:08:48,899
Na, pirmas kartas, kai mes
apskaičiuoti Mediana

199
00:08:48,899 --> 00:08:50,190
randame tai, ką mes ieškome.

200
00:08:50,190 --> 00:08:52,150
Iš viso praėjusiais
pavyzdžių, dvejetainis paieškos

201
00:08:52,150 --> 00:08:55,489
mes ką tik perėjo, jei mes turėjome
ieškojau elemento 15

202
00:08:55,489 --> 00:08:57,030
mes būtų nustatyta, kad iš karto.

203
00:08:57,030 --> 00:08:58,321
Tai buvo pačioje pradžioje.

204
00:08:58,321 --> 00:09:01,200
Tai buvo Mediana
pirmasis bandymas dalimis

205
00:09:01,200 --> 00:09:03,950
iš į dvejetainį paieškos pasidalijimas.

206
00:09:03,950 --> 00:09:06,350
>> Ir taip blogiausia
atveju dvejetainis paieškos tęsiasi

207
00:09:06,350 --> 00:09:11,580
į log n, kuri iš esmės geriau
nei tiesinės paieškoje, blogiausiu atveju.

208
00:09:11,580 --> 00:09:16,210
Geriausiu atveju dvejetainis
Paieška eina omega 1.

209
00:09:16,210 --> 00:09:18,990
Taigi dvejetainis paieškos yra daug
geriau nei tiesinės paieškos,

210
00:09:18,990 --> 00:09:23,270
bet jūs turite elgtis su proceso
rūšiavimas masyvo pirmą kartą prieš jūs galite

211
00:09:23,270 --> 00:09:26,140
sverto dvejetainis paieškos galią.

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

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

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