1
00:00:00,000 --> 00:00:03,346
>> [Muusika mängib]

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

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

4
00:00:06,220 --> 00:00:08,140
Nii Kahendotsingupuu on
algoritmi saame kasutada

5
00:00:08,140 --> 00:00:10,530
leida elemendi sees massiivi.

6
00:00:10,530 --> 00:00:14,710
Erinevalt lineaarne otsing, see nõuab
eritingimuse olema täidetud enne,

7
00:00:14,710 --> 00:00:19,020
aga see on nii palju tõhusam, kui
see tingimus on tegelikult täidetud.

8
00:00:19,020 --> 00:00:20,470
>> Mis siis mõte siin?

9
00:00:20,470 --> 00:00:21,780
see on jaga ja valitse.

10
00:00:21,780 --> 00:00:25,100
Me tahame vähendada suurus
otsingu ala poole võrra iga kord,

11
00:00:25,100 --> 00:00:27,240
et leida sihtmärk number.

12
00:00:27,240 --> 00:00:29,520
See on koht, kus see tingimus
tuleb mängu, kuigi.

13
00:00:29,520 --> 00:00:32,740
Me võime ainult võimendavat võimu
kaotades pool elemendid

14
00:00:32,740 --> 00:00:36,070
isegi ilma vaadates
neid, kui massiiv on järjestatud.

15
00:00:36,070 --> 00:00:39,200
>> Kui see on täielik mix up,
Me ei saa lihtsalt käest

16
00:00:39,200 --> 00:00:42,870
visake poole elemente, sest
Me ei tea, mida me sellest vabaneda.

17
00:00:42,870 --> 00:00:45,624
Aga kui massiiv on järjestatud,
saame teha, sest me

18
00:00:45,624 --> 00:00:48,040
tean, et kõik on
vasakule, kus me praegu oleme

19
00:00:48,040 --> 00:00:50,500
peab olema väiksem kui
väärtus oleme praegu.

20
00:00:50,500 --> 00:00:52,300
Ja kõik, et
õigust, kus me oleme

21
00:00:52,300 --> 00:00:55,040
peab olema suurem kui väärtus
me praegu vaadates.

22
00:00:55,040 --> 00:00:58,710
>> Mis siis pseudokoodi
sammud Kahendotsingupuu?

23
00:00:58,710 --> 00:01:02,310
Me kordame seda protsessi, kuni
massiiv või kui astume läbi,

24
00:01:02,310 --> 00:01:07,740
sub massiivid, väiksemateks tükkideks
originaal massiivi, on suurus 0.

25
00:01:07,740 --> 00:01:10,960
Arvuta keskpunktis
Praeguse alamjärjestuse.

26
00:01:10,960 --> 00:01:14,460
>> Kui väärtus, mida otsid, on
et massiivi element, peatus.

27
00:01:14,460 --> 00:01:15,030
Sa leidsid.

28
00:01:15,030 --> 00:01:16,550
See on suurepärane.

29
00:01:16,550 --> 00:01:19,610
Vastasel juhul, kui eesmärgiks on
vähem, kui on keskel,

30
00:01:19,610 --> 00:01:23,430
nii et kui väärtus ootame
on madalam kui see, mida me näeme,

31
00:01:23,430 --> 00:01:26,780
Seda protsessi korratakse taas, kuid
muuta lõpp-punkti, vaid

32
00:01:26,780 --> 00:01:29,300
olemise originaal
täitma täies massiiv,

33
00:01:29,300 --> 00:01:34,110
olla lihtsalt vasakule
kus me lihtsalt vaatasin.

34
00:01:34,110 --> 00:01:38,940
>> Me teadsime, et keset oli liiga kõrge,
või siht oli alla keskmise,

35
00:01:38,940 --> 00:01:42,210
ja nii see peab eksisteerima kui see
üldse eksisteerib massiiv,

36
00:01:42,210 --> 00:01:44,660
kusagil vasakul keskpunktis.

37
00:01:44,660 --> 00:01:48,120
Ja nii me määrata massiivi
Vaid vasakule

38
00:01:48,120 --> 00:01:51,145
keskpunkti uueks lõpp-punkti.

39
00:01:51,145 --> 00:01:53,770
Vastupidisel juhul, kui eesmärgiks on
suurem kui see, mida on keskel,

40
00:01:53,770 --> 00:01:55,750
meil täpselt sama
Meetod, kuid selle asemel me

41
00:01:55,750 --> 00:01:59,520
muuta alguspunkt olla
lihtsalt paremal keskpunktis

42
00:01:59,520 --> 00:02:00,680
me lihtsalt arvutada.

43
00:02:00,680 --> 00:02:03,220
Ja siis me protsessi uuesti alustama.

44
00:02:03,220 --> 00:02:05,220
>> Teeme seda visualiseerida, OK?

45
00:02:05,220 --> 00:02:08,620
Nii et palju läheb ja siin,
kuid siin hulgaliselt 15 elementi.

46
00:02:08,620 --> 00:02:11,400
Ja me ei kavatse olla kursis hoida
on palju rohkem asju seekord.

47
00:02:11,400 --> 00:02:13,870
Nii lineaarne otsing olime
lihtsalt hooliv sihtmärk.

48
00:02:13,870 --> 00:02:15,869
Aga seekord me tahame
hoolivad, kus me oleme

49
00:02:15,869 --> 00:02:18,480
hakkame vaatama, kus
me lõpetamist vaadates,

50
00:02:18,480 --> 00:02:21,876
ja mis on keskpunktis
Praeguse massiivi.

51
00:02:21,876 --> 00:02:23,250
Nii et siin me läheme Kahendotsingupuu.

52
00:02:23,250 --> 00:02:25,290
Oleme päris palju hea minna, eks?

53
00:02:25,290 --> 00:02:28,650
Ma lihtsalt panema
Alljärgnevalt kogum näitajaid.

54
00:02:28,650 --> 00:02:32,430
See on põhimõtteliselt just see element
massiivi me räägime.

55
00:02:32,430 --> 00:02:34,500
Mis lineaarne otsing me
huvita, sest me

56
00:02:34,500 --> 00:02:36,800
vaja teada, kui palju
elementide me iterating üle,

57
00:02:36,800 --> 00:02:40,010
aga me tegelikult ei huvita, mida
element me praegu vaadates.

58
00:02:40,010 --> 00:02:41,014
In Kahendotsingupuu, mida me teeme.

59
00:02:41,014 --> 00:02:42,930
Ja nii need on vaid
seal nagu väike juhend.

60
00:02:42,930 --> 00:02:44,910
>> Nii saame alustada, eks?

61
00:02:44,910 --> 00:02:46,240
Noh, mitte päris.

62
00:02:46,240 --> 00:02:48,160
Pea meeles, mida ma ütlesin
umbes Kahendotsingupuu?

63
00:02:48,160 --> 00:02:50,955
Me ei saa seda teha kohta
sorteerimata massiivi või muud,

64
00:02:50,955 --> 00:02:55,820
me ei taga, et
teatud elemente või väärtused ei ole

65
00:02:55,820 --> 00:02:57,650
Juhuslike
visata, kui me lihtsalt

66
00:02:57,650 --> 00:02:59,920
otsustab ignoreerida pool massiivi.

67
00:02:59,920 --> 00:03:02,574
>> Nii samm üks binaarne otsing
on sul peab olema järjestatud hulga.

68
00:03:02,574 --> 00:03:05,240
Ja mida saab kasutada ükskõik millise sorteerimine
algoritme me rääkisime

69
00:03:05,240 --> 00:03:06,700
sulle seda seisukohta.

70
00:03:06,700 --> 00:03:10,370
Nüüd, oleme olukorras, kus
saame täita Kahendotsingupuu.

71
00:03:10,370 --> 00:03:12,560
>> Nii saab protsessi korrata
Samm-sammult ja hoida

72
00:03:12,560 --> 00:03:14,830
jälgida, mis toimub nagu me minna.

73
00:03:14,830 --> 00:03:17,980
Nii et esimese peame tegema, on arvutada
keskpunktis praeguse massiivi.

74
00:03:17,980 --> 00:03:20,620
Noh, ütleme me, esimene
kõik, kes otsivad väärtus 19.

75
00:03:20,620 --> 00:03:22,290
Me püüame leida number 19.

76
00:03:22,290 --> 00:03:25,380
Esimene element käesoleva
massiiv asub index null,

77
00:03:25,380 --> 00:03:28,880
ja viimane osa sellest
massiiv asub indeks 14.

78
00:03:28,880 --> 00:03:31,430
Ja nii me kutsume neid alguse ja lõpu.

79
00:03:31,430 --> 00:03:35,387
>> Nii me arvutada keskpunktis poolt
Lisades 0 pluss 14 jagatud 2;

80
00:03:35,387 --> 00:03:36,720
üsna lihtne keskpunktis.

81
00:03:36,720 --> 00:03:40,190
Ja me ei saa öelda, et
keskpunktis on nüüd 7.

82
00:03:40,190 --> 00:03:43,370
Nii on 15, mida me otsime?

83
00:03:43,370 --> 00:03:43,940
Ei see ei ole.

84
00:03:43,940 --> 00:03:45,270
Otsime 19.

85
00:03:45,270 --> 00:03:49,400
Aga me teame, et 19 on suurem
kui see, mida me leidsime keskel.

86
00:03:49,400 --> 00:03:52,470
>> Mida me saame teha, on
muuta alguspunkt

87
00:03:52,470 --> 00:03:57,280
olema lihtsalt paremal
keskpunktis, ja korrake protsessi uuesti.

88
00:03:57,280 --> 00:04:01,690
Ja kui me seda teeme, oleme nüüd öelda
uus alguspunkt on massiiv asukoha 8.

89
00:04:01,690 --> 00:04:07,220
Mida me oleme tegelikult teinud on
ignoreeritakse kõike vasakul 15.

90
00:04:07,220 --> 00:04:09,570
Me oleme kõrvaldanud poole
probleemi, ja nüüd,

91
00:04:09,570 --> 00:04:13,510
selle asemel, et otsida
Üle 15 elementi meie massiiv,

92
00:04:13,510 --> 00:04:15,610
meil on ainult otsida üle 7.

93
00:04:15,610 --> 00:04:17,706
Nii 8 on uus alguspunkt.

94
00:04:17,706 --> 00:04:19,600
14 on ikka lõpp-punkti.

95
00:04:19,600 --> 00:04:21,430
>> Ja nüüd, me läheme üle selle uuesti.

96
00:04:21,430 --> 00:04:22,810
Me arvutame uue keskpunkti.

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

98
00:04:27,130 --> 00:04:28,660
Kas see, mida me otsime?

99
00:04:28,660 --> 00:04:30,110
Ei see ei ole.

100
00:04:30,110 --> 00:04:32,930
Otsime väärtus, mis on
vähem kui see, mida me lihtsalt leida.

101
00:04:32,930 --> 00:04:34,721
Nii et me läheme kordama
protsessi uuesti.

102
00:04:34,721 --> 00:04:38,280
Me läheme muuta lõpp-punkt
olla just vasakul keskpunktis.

103
00:04:38,280 --> 00:04:41,800
Nii et uue lõpp-punkt muutub 10.

104
00:04:41,800 --> 00:04:44,780
Ja nüüd, see on ainult osa
massiivi meil sorteeri.

105
00:04:44,780 --> 00:04:48,460
Nii oleme nüüd kõrvaldatud
12 15 elementi.

106
00:04:48,460 --> 00:04:51,550
Me teame, et kui 19
olemas massiiv, siis

107
00:04:51,550 --> 00:04:57,210
peab olemas olema kusagil element
number 8 ja element number 10.

108
00:04:57,210 --> 00:04:59,400
>> Nii me arvutada uue keskpunkti uuesti.

109
00:04:59,400 --> 00:05:02,900
8 pluss 10 on 18 jagatuna 2 on 9.

110
00:05:02,900 --> 00:05:05,074
Ja sel juhul, otsida, siis
Eesmärgiks on keskel.

111
00:05:05,074 --> 00:05:06,740
Leidsime täpselt, mida me otsime.

112
00:05:06,740 --> 00:05:07,780
Me ei saa peatada.

113
00:05:07,780 --> 00:05:10,561
Me edukalt
binaarne otsing.

114
00:05:10,561 --> 00:05:11,060
Hästi.

115
00:05:11,060 --> 00:05:13,930
Nii et me teame, et see algoritm
töötab kui eesmärgiks on

116
00:05:13,930 --> 00:05:16,070
kusagil sees massiiv.

117
00:05:16,070 --> 00:05:19,060
Kas see algoritm töö kui
eesmärk ei ole massiivi?

118
00:05:19,060 --> 00:05:20,810
Noh, alustame siis
uuesti ja seekord

119
00:05:20,810 --> 00:05:23,380
Vaatame elemendi
16, mis visuaalselt näeme

120
00:05:23,380 --> 00:05:25,620
ei ole kuhugi massiivi.

121
00:05:25,620 --> 00:05:27,110
>> Alguspunkt on jälle 0.

122
00:05:27,110 --> 00:05:28,590
Lõpp-punkt on jälle 14.

123
00:05:28,590 --> 00:05:32,490
Need on indeksid esimese ja
viimase elementide täielik array.

124
00:05:32,490 --> 00:05:36,057
Ja me minna läbi protsessi me lihtsalt
läbis uuesti, püüdes leida 16

125
00:05:36,057 --> 00:05:39,140
kuigi visuaalselt, saame juba
öelda, et ta ei kavatse olla seal.

126
00:05:39,140 --> 00:05:43,450
Me lihtsalt tahame veenduda selle algoritmi
siis tegelikult töötavad endiselt mingil moel

127
00:05:43,450 --> 00:05:46,310
ja ei jäta meile
kinni lõputu silmuse.

128
00:05:46,310 --> 00:05:48,190
>> Mis siis samm esimesena?

129
00:05:48,190 --> 00:05:50,230
Arvuta keskpunktis
Praeguse massiivi.

130
00:05:50,230 --> 00:05:52,790
Mis keskpunktis
Praeguse massiivi?

131
00:05:52,790 --> 00:05:54,410
Noh, see on 7, eks?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 jagatuna 2 on 7.

133
00:05:57,560 --> 00:05:59,280
Kas 15, mida me otsime?

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

135
00:05:59,780 --> 00:06:02,930
See on üsna lähedal, kuid ootame
jaoks väärtus veidi suurem kui see.

136
00:06:02,930 --> 00:06:06,310
>> Nii et me teame, et see läheb
saab kuhugi vasakul 15.

137
00:06:06,310 --> 00:06:08,540
Eesmärk on suurem kui
Mis keskpunktis.

138
00:06:08,540 --> 00:06:12,450
Ja nii me seame uue alguspunkti
just paremal keskel.

139
00:06:12,450 --> 00:06:16,130
Keskpunktis on praegu 7, nii et
oletame uus alguspunkt on 8.

140
00:06:16,130 --> 00:06:18,130
Ja me oleme tegelikult
kordama ignoreeritakse

141
00:06:18,130 --> 00:06:21,150
kogu vasak pool massiivi.

142
00:06:21,150 --> 00:06:23,750
>> Nüüd, me kordame
töödelda veel üks kord.

143
00:06:23,750 --> 00:06:24,910
Arvutage uue keskpunkti.

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

145
00:06:29,350 --> 00:06:31,060
Kas 23, mida me otsime?

146
00:06:31,060 --> 00:06:31,870
Kahjuks mitte.

147
00:06:31,870 --> 00:06:34,930
Otsime väärtus
mis on väiksem kui 23.

148
00:06:34,930 --> 00:06:37,850
Ja nii sel juhul, me ei kavatse
muuta lõpp-punkt on lihtsalt

149
00:06:37,850 --> 00:06:40,035
vasakul praeguse keskpunktis.

150
00:06:40,035 --> 00:06:43,440
Praegune keskpunktis on 11, ja
nii me seada uusi lõpp-punkti

151
00:06:43,440 --> 00:06:46,980
järgmine kord läheme
selle protsessi kaudu 10.

152
00:06:46,980 --> 00:06:48,660
>> Jällegi, me minna läbi protsessi uuesti.

153
00:06:48,660 --> 00:06:49,640
Arvuta keskpunktis.

154
00:06:49,640 --> 00:06:53,100
8 pluss 10 jagatud 2 on 9.

155
00:06:53,100 --> 00:06:54,750
Kas 19, mida me otsime?

156
00:06:54,750 --> 00:06:55,500
Kahjuks mitte.

157
00:06:55,500 --> 00:06:58,050
Me otsid veel
number väiksem.

158
00:06:58,050 --> 00:07:02,060
Nii muudame lõpp-punkti seekord
olevat vaid vasakul keskpunktis.

159
00:07:02,060 --> 00:07:05,532
Keskpunktis on praegu 9,
nii lõpp-punkt on 8.

160
00:07:05,532 --> 00:07:07,920
Ja nüüd, me lihtsalt otsin
ühes element massiivi.

161
00:07:07,920 --> 00:07:10,250
>> Mis keskpunktis seda valikut?

162
00:07:10,250 --> 00:07:13,459
Noh, see algab kell 8, siis
lõpeb kell 8, keskpunktis on 8.

163
00:07:13,459 --> 00:07:14,750
Kas see, mida me otsime?

164
00:07:14,750 --> 00:07:16,339
Kas me otsime 17?

165
00:07:16,339 --> 00:07:17,380
Ei, me otsitavat 16.

166
00:07:17,380 --> 00:07:20,160
Nii et kui see on olemas massiiv,
see peab olemas olema kuskil

167
00:07:20,160 --> 00:07:21,935
vasakul kus me praegu oleme.

168
00:07:21,935 --> 00:07:23,060
Mida me siis teeme?

169
00:07:23,060 --> 00:07:26,610
Noh, me määrata lõpp-punkt on lihtsalt
vasakul praeguse keskpunktis.

170
00:07:26,610 --> 00:07:29,055
Nii muudame lõpp-punkt 7.

171
00:07:29,055 --> 00:07:32,120
Kas sa näed, mida lihtsalt
siin juhtus, kuigi?

172
00:07:32,120 --> 00:07:33,370
Vaata siin nüüd.

173
00:07:33,370 --> 00:07:35,970
>> Start on nüüd suurem kui lõpus.

174
00:07:35,970 --> 00:07:39,620
Tõhusalt on kaks otsa
meie massiivi ületanud,

175
00:07:39,620 --> 00:07:42,252
ja alguspunkt on
nüüd pärast punkti.

176
00:07:42,252 --> 00:07:43,960
Noh, et ei
mingit mõtet, eks?

177
00:07:43,960 --> 00:07:47,960
Nüüd, mida me ei saa öelda, me
on sub massiivi suurus 0.

178
00:07:47,960 --> 00:07:50,110
Ja kui me õppinud
Sel hetkel, saame nüüd

179
00:07:50,110 --> 00:07:53,940
tagada, et element 16
ei ole olemas massiiv,

180
00:07:53,940 --> 00:07:56,280
sest alguspunkt
ja lõpp-punkti ületanud.

181
00:07:56,280 --> 00:07:58,340
Ja nii see ei ole.

182
00:07:58,340 --> 00:08:01,340
Nüüd, märkate, et see on veidi
teistsugune kui alguspunkt ja lõpp

183
00:08:01,340 --> 00:08:02,900
juhtida on sama.

184
00:08:02,900 --> 00:08:05,030
Kui me otsinud
17, see oleks

185
00:08:05,030 --> 00:08:08,870
olnud massiivi ning alguspunkt
ja lõpp-punkt, et viimase iteratsiooni

186
00:08:08,870 --> 00:08:11,820
Enne neid punkte ületanud,
meil oleks olnud 17 seal.

187
00:08:11,820 --> 00:08:15,510
See on ainult siis, kui nad ületavad et suudame
tagada, et andmeid ei ole

188
00:08:15,510 --> 00:08:17,180
olemas massiiv.

189
00:08:17,180 --> 00:08:20,260
>> Võtame palju vähem
samme kui lineaarne otsing.

190
00:08:20,260 --> 00:08:23,250
In halvimal juhul oli meil
lahku nimekirja n elemendid

191
00:08:23,250 --> 00:08:27,770
korduvalt pooleks leida sihtmärk,
kas sellepärast, et siht element

192
00:08:27,770 --> 00:08:33,110
kusagil viimase
jagunemise või seda ei ole olemas üldse.

193
00:08:33,110 --> 00:08:37,830
Nii et halvimal juhul tuleb meil
lahku array-- sa tead?

194
00:08:37,830 --> 00:08:40,510
Logi n korda; me
on vähendada probleemi

195
00:08:40,510 --> 00:08:42,610
pooleks teatud arv kordi.

196
00:08:42,610 --> 00:08:45,160
See, mitu korda on log n.

197
00:08:45,160 --> 00:08:46,510
>> Milline on parim stsenaarium?

198
00:08:46,510 --> 00:08:48,899
Noh, esimene kord, kui me
arvutada keskpunktis,

199
00:08:48,899 --> 00:08:50,190
leiame, mida me otsime.

200
00:08:50,190 --> 00:08:52,150
Kõikidel eelmise
näiteid Kahendotsingupuu

201
00:08:52,150 --> 00:08:55,489
oleme läinud üle, kui meil oleks
otsinud element 15,

202
00:08:55,489 --> 00:08:57,030
me leidsime, et kohe.

203
00:08:57,030 --> 00:08:58,321
See oli alguses.

204
00:08:58,321 --> 00:09:01,200
See oli keskpunktis
esimene katse lõhestatud

205
00:09:01,200 --> 00:09:03,950
Jaoskonnakomisjoni binaarne otsing.

206
00:09:03,950 --> 00:09:06,350
>> Ja nii halvimal
Juhul, Kahendotsingupuu jookseb

207
00:09:06,350 --> 00:09:11,580
log n, mis on märksa paremini
kui lineaarset otsingut, halvimal juhul.

208
00:09:11,580 --> 00:09:16,210
Parimal juhul binaarne
Otsing töötab omega 1.

209
00:09:16,210 --> 00:09:18,990
Nii Kahendotsingupuu on palju
parem kui lineaarne otsing,

210
00:09:18,990 --> 00:09:23,270
aga sa pead tegelema protsessi
sorteerimine oma rida, enne kui saab

211
00:09:23,270 --> 00:09:26,140
võimendavat võimu Kahendotsingupuu.

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

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

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