1
00:00:00,000 --> 00:00:03,346
>> [MUZIKO Ludante]

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

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

4
00:00:06,220 --> 00:00:08,140
Do duuma serĉo estas
algoritmo ni povas uzi

5
00:00:08,140 --> 00:00:10,530
trovi elementon ene de tabelo.

6
00:00:10,530 --> 00:00:14,710
Kontraste lineara serĉo, ĝi postulas
speciala kondiĉo esti renkontita antemano,

7
00:00:14,710 --> 00:00:19,020
sed estas tiel multe pli efika se
ke kondiĉo estas, fakte, renkontis.

8
00:00:19,020 --> 00:00:20,470
>> Do kio estas la ideo tie?

9
00:00:20,470 --> 00:00:21,780
ĝi estas dividi kaj venki.

10
00:00:21,780 --> 00:00:25,100
Ni volas redukti la grandecon de
la serĉo spaco por duono ĉiufoje

11
00:00:25,100 --> 00:00:27,240
por trovi celan nombron.

12
00:00:27,240 --> 00:00:29,520
Jen kie tiu kondiĉo
havas rolon, kvankam.

13
00:00:29,520 --> 00:00:32,740
Ni povas nur utiligi la povon de
forigi duonon de la elementoj

14
00:00:32,740 --> 00:00:36,070
sen eĉ rigardi
ili se la tabelo estas ordigita.

15
00:00:36,070 --> 00:00:39,200
>> Se ĝi estas kompleta miksaĵo supren,
Ni ne povas nur el mano

16
00:00:39,200 --> 00:00:42,870
forĵeti duonon el la elementoj, ĉar
ni ne scias kion ni forĵeti.

17
00:00:42,870 --> 00:00:45,624
Sed se la tabelo estas ordigita,
ni povas fari tion, ĉar ni

18
00:00:45,624 --> 00:00:48,040
scias ke ĉiu al la
lasita de kie ni nune estas

19
00:00:48,040 --> 00:00:50,500
devas esti pli malalta ol la
valoro ni estas nune en.

20
00:00:50,500 --> 00:00:52,300
Kaj ĉiu al la
rajto de kie ni estas

21
00:00:52,300 --> 00:00:55,040
devas esti pli granda ol la valoro
ni nuntempe rigardante.

22
00:00:55,040 --> 00:00:58,710
>> Do kio estas la _pseudocode_
paŝojn por duuma serĉo?

23
00:00:58,710 --> 00:01:02,310
Ni ripeti ĉi procezo ĝis la
tabelo aŭ, kiel ni procedas tra,

24
00:01:02,310 --> 00:01:07,740
Sub arrays, malgrandaj pecoj de
la origina tabelo estas de amplekso 0.

25
00:01:07,740 --> 00:01:10,960
Kalkuli la mezpunkto
de la aktuala sub tabelo.

26
00:01:10,960 --> 00:01:14,460
>> Se la valoro vi serĉas estas
en tiu ero de la tabelo, ĉesi.

27
00:01:14,460 --> 00:01:15,030
Vi trovis ĝin.

28
00:01:15,030 --> 00:01:16,550
Tio estas granda.

29
00:01:16,550 --> 00:01:19,610
Alie, se la celo estas
malpli ol kio estas en la mezo,

30
00:01:19,610 --> 00:01:23,430
do se la valoro ni serĉas
cxar estas pli malalta ol kion ni vidas,

31
00:01:23,430 --> 00:01:26,780
Ripeti ĉi procezo denove, sed
ŝanĝi la fina punkto, anstataŭ

32
00:01:26,780 --> 00:01:29,300
esti la originalo
kompletigi plena tabelo,

33
00:01:29,300 --> 00:01:34,110
esti ĵus maldekstren
de kie ni nur rigardis.

34
00:01:34,110 --> 00:01:38,940
>> Ni sciis ke la meza havis tro alta,
aŭ la celo estis malpli ol la duono,

35
00:01:38,940 --> 00:01:42,210
kaj do devas ekzisti, se ĝi
ekzistas tute en la tabelo,

36
00:01:42,210 --> 00:01:44,660
ie maldekstren de la mezpunkto.

37
00:01:44,660 --> 00:01:48,120
Kaj tial ni starigu la tabelo
situon ĝuste maldekstren

38
00:01:48,120 --> 00:01:51,145
de la mezpunkto kiel nova fina punkto.

39
00:01:51,145 --> 00:01:53,770
Male, se la celo estas
pli granda ol kio estas en la mezo,

40
00:01:53,770 --> 00:01:55,750
ni faru la samajn
procezo, sed anstataŭe ni

41
00:01:55,750 --> 00:01:59,520
ŝanĝi la komenco punkto esti
iom dekstre de la mezpunkto

42
00:01:59,520 --> 00:02:00,680
ni simple kalkulas.

43
00:02:00,680 --> 00:02:03,220
Kaj tiam, ni komencos la procezon denove.

44
00:02:03,220 --> 00:02:05,220
>> Ni bildigi tion, OK?

45
00:02:05,220 --> 00:02:08,620
Do ekzistas multe iranta kaj ĉi tie,
sed ĉi tie estas tabelo de la 15 elementoj.

46
00:02:08,620 --> 00:02:11,400
Kaj ni tuj estos konservanta trako
de multaj pli aĵoj ĉi tempo.

47
00:02:11,400 --> 00:02:13,870
Do en lineara serĉo, ni estis
nur zorgi pri celo.

48
00:02:13,870 --> 00:02:15,869
Sed ĉifoje ni volas
zorgi pri kie ni estas

49
00:02:15,869 --> 00:02:18,480
komencanta rigardi, kie
ni haltas rigardanta,

50
00:02:18,480 --> 00:02:21,876
kaj kio estas la mezpunkto
de la nuna tabelo.

51
00:02:21,876 --> 00:02:23,250
Do jen ni iros kun duuma serĉo.

52
00:02:23,250 --> 00:02:25,290
Ni estas sufiĉe tre bona iri, ĉu ne?

53
00:02:25,290 --> 00:02:28,650
Mi simple tuj meti malsupren
sube tie aro de indeksoj.

54
00:02:28,650 --> 00:02:32,430
Tiu estas esence nur kion elemento
de la tabelo ni parolas.

55
00:02:32,430 --> 00:02:34,500
Kun lineara serĉo, ni
zorgas, ĉar ni

56
00:02:34,500 --> 00:02:36,800
bezonas scii kiom da
elementoj ni ripetanta super,

57
00:02:36,800 --> 00:02:40,010
sed ni ne vere gravas kio
elementon ni aktuale rigardante.

58
00:02:40,010 --> 00:02:41,014
En duuma serĉo, ni faros.

59
00:02:41,014 --> 00:02:42,930
Kaj tial tiuj estas nur
tie kiel malgranda gvidas.

60
00:02:42,930 --> 00:02:44,910
>> Do ni povas starti, dekstra?

61
00:02:44,910 --> 00:02:46,240
Nu, ne tute.

62
00:02:46,240 --> 00:02:48,160
Memoru kion mi diris
pri duuma serĉo?

63
00:02:48,160 --> 00:02:50,955
Ni ne povas fari ĝin sur
unsorted tabelo aux,

64
00:02:50,955 --> 00:02:55,820
ni ne garantiante ke la
iuj elementoj aŭ valoroj ne

65
00:02:55,820 --> 00:02:57,650
esti hazarde
forĵetitaj kiam ni ĵus

66
00:02:57,650 --> 00:02:59,920
decidas ignori duono de la tabelo.

67
00:02:59,920 --> 00:03:02,574
>> Do paŝi unu kun duuma serĉo
estas vi devas havi ordo tabelo.

68
00:03:02,574 --> 00:03:05,240
Kaj vi povas uzi ajnan el la ordigado
algoritmoj ni parolis pri

69
00:03:05,240 --> 00:03:06,700
akiri vin al tiu pozicio.

70
00:03:06,700 --> 00:03:10,370
Do nun, ni estas en pozicio kie
ni povas elfari duuma serĉo.

71
00:03:10,370 --> 00:03:12,560
>> Do ni ripeti la procezon
paŝon post paŝo kaj teni

72
00:03:12,560 --> 00:03:14,830
trako de kio okazas dum ni marŝos.

73
00:03:14,830 --> 00:03:17,980
Do la unua ni devas fari estas kalkuli
la mezpunkto de la nuna tabelo.

74
00:03:17,980 --> 00:03:20,620
Nu, ni diras, ke ni estas, unue
ĉiuj, serĉante la valoro 19.

75
00:03:20,620 --> 00:03:22,290
Ni provas trovi la nombron 19.

76
00:03:22,290 --> 00:03:25,380
La unua elemento de tiu
tabelo situas ĉe indeksa nulo,

77
00:03:25,380 --> 00:03:28,880
kaj la lasta elemento de tiu
tabelo situas ĉe indekso 14.

78
00:03:28,880 --> 00:03:31,430
Kaj do ni nomas tiujn komenco kaj fino.

79
00:03:31,430 --> 00:03:35,387
>> Do ni kalkuli la mezpunkto de
aldonante 0 plus 14 dividite per 2;

80
00:03:35,387 --> 00:03:36,720
bela simpla mezpunkto.

81
00:03:36,720 --> 00:03:40,190
Kaj ni povas diri ke
la mezpunkto estas nun 7.

82
00:03:40,190 --> 00:03:43,370
Do estas 15 kion ni serĉas?

83
00:03:43,370 --> 00:03:43,940
Ne, ĝi ne estas.

84
00:03:43,940 --> 00:03:45,270
Ni serĉas 19.

85
00:03:45,270 --> 00:03:49,400
Sed ni scias, ke 19 estas pli granda
ol kion ni konstatis en la mezo.

86
00:03:49,400 --> 00:03:52,470
>> Do kion ni povas fari estas
ŝanĝi la komenco punkto

87
00:03:52,470 --> 00:03:57,280
esti iom dekstre de la
mezpunkto, kaj ripeti la procezon denove.

88
00:03:57,280 --> 00:04:01,690
Kiam ni faras tion, ni nun diru la
nova komenco punkto estas tabelo situon 8.

89
00:04:01,690 --> 00:04:07,220
Kion ni efektive faris estas
ignoris ĉion al la maldekstra de 15.

90
00:04:07,220 --> 00:04:09,570
Ni forigas duonon
de la problemo, kaj nun,

91
00:04:09,570 --> 00:04:13,510
anstataŭ devi serĉi
super 15 elementoj en nia tabelo,

92
00:04:13,510 --> 00:04:15,610
ni nur devas serĉi pli ol 7.

93
00:04:15,610 --> 00:04:17,706
Do 8 estas la nova komenco punkto.

94
00:04:17,706 --> 00:04:19,600
14 estas ankoraŭ la fino punkto.

95
00:04:19,600 --> 00:04:21,430
>> Kaj nun ni transiru ĉi denove.

96
00:04:21,430 --> 00:04:22,810
Ni kalkulas la nova mezpunkto.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 estas 22 dividita per 2 estas 11.

98
00:04:27,130 --> 00:04:28,660
Ĉu tio kion ni serĉas?

99
00:04:28,660 --> 00:04:30,110
Ne, ĝi ne estas.

100
00:04:30,110 --> 00:04:32,930
Ni serĉas valoron tio
malpli ol kion ni ĵus trovis.

101
00:04:32,930 --> 00:04:34,721
Do ni tuj ripetas
la procezon denove.

102
00:04:34,721 --> 00:04:38,280
Ni tuj ŝanĝi la ekstrema punkto por
estos precize la maldekstra de la mezpunkto.

103
00:04:38,280 --> 00:04:41,800
Do la nova fina punkto iĝas 10.

104
00:04:41,800 --> 00:04:44,780
Kaj nun, tio estas la sola parto de
la tabelo ni devas ordigi tra.

105
00:04:44,780 --> 00:04:48,460
Do ni jam forigita
12 el la 15 elementoj.

106
00:04:48,460 --> 00:04:51,550
Ni scias ke se 19
Ekzistas en la tabelo, ĝi

107
00:04:51,550 --> 00:04:57,210
devas ekzisti ie inter elemento
numero 8 kaj elemento numero 10.

108
00:04:57,210 --> 00:04:59,400
>> Do ni kalkulas la nova mezpunkto denove.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 estas 18 dividita per 2 estas 9.

110
00:05:02,900 --> 00:05:05,074
Kaj en ĉi tiu kazo, rigardu, la
celo estas ĉe la mezo.

111
00:05:05,074 --> 00:05:06,740
Ni trovis ĝuste kion ni serĉas.

112
00:05:06,740 --> 00:05:07,780
Ni povas haltigi.

113
00:05:07,780 --> 00:05:10,561
Ni sukcese kompletigitaj
duuma serĉo.

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

115
00:05:11,060 --> 00:05:13,930
Do ni scias ĉi algoritmo
funkcias se la celo estas

116
00:05:13,930 --> 00:05:16,070
ie interne de la tabelo.

117
00:05:16,070 --> 00:05:19,060
Ĉu tiu algoritmo laboro se
la celo ne estas en la tabelo?

118
00:05:19,060 --> 00:05:20,810
Nu, ni komencu gxin
denove, kaj tiu tempon,

119
00:05:20,810 --> 00:05:23,380
ni serĉas la elemento
16, kiu vide povas vidi

120
00:05:23,380 --> 00:05:25,620
ne ekzistas ie en la tabelo.

121
00:05:25,620 --> 00:05:27,110
>> La komenco punkto estas denove 0.

122
00:05:27,110 --> 00:05:28,590
La fina punkto estas denove 14.

123
00:05:28,590 --> 00:05:32,490
Tiuj estas la indeksoj de la unua kaj
lastaj elementoj de la kompleta tabelo.

124
00:05:32,490 --> 00:05:36,057
Kaj ni iros tra la procezo ni ĵus
trairis denove, provante trovi la 16

125
00:05:36,057 --> 00:05:39,140
kvankam vide, ni povas jam
diru ke ĝi ne tuj estos tie.

126
00:05:39,140 --> 00:05:43,450
Ni nur volas certigi tiun algoritmon
estos, fakte, ankoraŭ labori iel

127
00:05:43,450 --> 00:05:46,310
kaj ne nur lasi nin
senmoviĝita en senfina buklo.

128
00:05:46,310 --> 00:05:48,190
>> Do kio estas la paŝo unuan?

129
00:05:48,190 --> 00:05:50,230
Kalkuli la mezpunkto
de la nuna tabelo.

130
00:05:50,230 --> 00:05:52,790
Kio estas la mezpunkto
de la nuna tabelo?

131
00:05:52,790 --> 00:05:54,410
Nu, estas 7, dekstra?

132
00:05:54,410 --> 00:05:57,560
14 Plus 0 dividita per 2 estas 7.

133
00:05:57,560 --> 00:05:59,280
Estas 15 kion ni serĉas?

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

135
00:05:59,780 --> 00:06:02,930
Ĝi estas sufiĉe proksima, sed ni serĉas
por valoro iomete pli granda ol tio.

136
00:06:02,930 --> 00:06:06,310
>> Do ni scias, ke ĝi tuj
esti nenie maldekstren de 15.

137
00:06:06,310 --> 00:06:08,540
La celo estas pli granda ol
kio estas en la mezpunkto.

138
00:06:08,540 --> 00:06:12,450
Kaj tial ni starigu la nova komenco punkto
esti iom dekstre de la mezo.

139
00:06:12,450 --> 00:06:16,130
La mezpunkto estas nuntempe 7, do
diru la nova komenco punkto estas 8.

140
00:06:16,130 --> 00:06:18,130
Kaj kion ni efektive
faras: estas ignorataj

141
00:06:18,130 --> 00:06:21,150
la tuta maldekstra duono de la tabelo.

142
00:06:21,150 --> 00:06:23,750
>> Nun, ni ripetu la
procesi pli tempo.

143
00:06:23,750 --> 00:06:24,910
Kalkuli la nova mezpunkto.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 estas 22 dividita per 2 estas 11.

145
00:06:29,350 --> 00:06:31,060
Estas 23 kion ni serĉas?

146
00:06:31,060 --> 00:06:31,870
Bedaŭrinde, ne.

147
00:06:31,870 --> 00:06:34,930
Ni serĉas valoron
ke estas malpli ol 23.

148
00:06:34,930 --> 00:06:37,850
Kaj tiel en tiu kazo, ni tuj
ŝanĝi la ekstrema punkto por esti simple

149
00:06:37,850 --> 00:06:40,035
maldekstre de la nuna mezpunkto.

150
00:06:40,035 --> 00:06:43,440
La nuna mezpunkto estas 11, kaj
do ni starigis la nova fina punkto

151
00:06:43,440 --> 00:06:46,980
por la venonta fojo ni iros
tra ĉi tiu procezo al 10.

152
00:06:46,980 --> 00:06:48,660
>> Denove, ni iras tra la procezo denove.

153
00:06:48,660 --> 00:06:49,640
Kalkuli la mezpunkto.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 dividita per 2 estas 9.

155
00:06:53,100 --> 00:06:54,750
Estas 19 kion ni serĉas?

156
00:06:54,750 --> 00:06:55,500
Bedaŭrinde, ne.

157
00:06:55,500 --> 00:06:58,050
Ni ankoraŭ serĉas
nombro malpli ol tio.

158
00:06:58,050 --> 00:07:02,060
Do ni ŝanĝi la ekstrema punkto tiu tempo
esti ĵus maldekstren de la mezpunkto.

159
00:07:02,060 --> 00:07:05,532
La mezpunkto estas nuntempe 9,
tiel la fina punkto estos 8.

160
00:07:05,532 --> 00:07:07,920
Kaj nun, ni nur rigardis
ĉe ununura elemento tabelo.

161
00:07:07,920 --> 00:07:10,250
>> Kio estas la mezpunkto de tiu tabelo?

162
00:07:10,250 --> 00:07:13,459
Nu, ĝi komenciĝas ĉe 8, ĝi
finiĝas ĉe 8, la mezpunkto estas 8.

163
00:07:13,459 --> 00:07:14,750
Ĉu tio kion ni serĉas?

164
00:07:14,750 --> 00:07:16,339
Ĉu ni serĉas 17?

165
00:07:16,339 --> 00:07:17,380
Ne, ni serĉas 16.

166
00:07:17,380 --> 00:07:20,160
Do se ekzistas en la tabelo,
ĝi devas ekzisti ie

167
00:07:20,160 --> 00:07:21,935
maldekstren de kie ni nune estas.

168
00:07:21,935 --> 00:07:23,060
Do kion ni faros?

169
00:07:23,060 --> 00:07:26,610
Nu, ni starigis la ekstrema punkto por esti simple
maldekstre de la nuna mezpunkto.

170
00:07:26,610 --> 00:07:29,055
Do ni ŝanĝi la ekstrema punkto al 7.

171
00:07:29,055 --> 00:07:32,120
Ĉu vi vidas kion ĵus
okazis tie, kvankam?

172
00:07:32,120 --> 00:07:33,370
Rigardu ĉi tien nun.

173
00:07:33,370 --> 00:07:35,970
>> Komenci nun pli granda ol fino.

174
00:07:35,970 --> 00:07:39,620
Efike, la du flankoj
de nia tabelo transiris,

175
00:07:39,620 --> 00:07:42,252
kaj la komenco punkto estas
nun post la fina punkto.

176
00:07:42,252 --> 00:07:43,960
Nu, kiu ne
fari neniun senson, dekstra?

177
00:07:43,960 --> 00:07:47,960
Do nun, kion ni povas diri estas ni
havas sub- tabelo de amplekso 0.

178
00:07:47,960 --> 00:07:50,110
Kaj unufoje ni alvenis al
tiu punkto, ni povas nun

179
00:07:50,110 --> 00:07:53,940
garantii ke elemento 16
Ne ekzistas en la tabelo,

180
00:07:53,940 --> 00:07:56,280
ĉar la komenco punkto
kaj fina punkto transiris.

181
00:07:56,280 --> 00:07:58,340
Kaj tiel ĝi ne estas tie.

182
00:07:58,340 --> 00:08:01,340
Nun, rimarki ke tiu estas iomete
malsamaj ol la komenco punkto kaj fino

183
00:08:01,340 --> 00:08:02,900
atentigi esti la sama.

184
00:08:02,900 --> 00:08:05,030
Se ni estus rigardante
por 17, ĝi havus

185
00:08:05,030 --> 00:08:08,870
estis en la tabelo, kaj la komenco punkto
kaj fina punkto de tiu lasta ripeto

186
00:08:08,870 --> 00:08:11,820
antaŭ tiuj punktoj transiris,
ni estus trovita 17 tie.

187
00:08:11,820 --> 00:08:15,510
Ĝi estas nur kiam ili transiras ke ni povas
garantii ke la elemento ne

188
00:08:15,510 --> 00:08:17,180
ekzistas en la tabelo.

189
00:08:17,180 --> 00:08:20,260
>> Do ni multe malpli
paŝoj ol lineara serĉo.

190
00:08:20,260 --> 00:08:23,250
En la plej malbona kazo scenaro, ni devis
fendi liston de n elementoj

191
00:08:23,250 --> 00:08:27,770
ree en duono por trovi la celon,
ĉu ĉar la celo elemento

192
00:08:27,770 --> 00:08:33,110
estos ie en la lasta
divido, aŭ ĝi ne ekzistas.

193
00:08:33,110 --> 00:08:37,830
Do en la plej malbona kazo, ni devos
disigis la tabelo vi scias?

194
00:08:37,830 --> 00:08:40,510
Log de n fojojn; ni
devos tranĉi la problemon

195
00:08:40,510 --> 00:08:42,610
en duono certan nombron da fojoj.

196
00:08:42,610 --> 00:08:45,160
Ke plurfoje estas log n.

197
00:08:45,160 --> 00:08:46,510
>> Kio estas la plej bona kazo scenaro?

198
00:08:46,510 --> 00:08:48,899
Nu, la unuan fojon ni
kalkuli la mezpunkto,

199
00:08:48,899 --> 00:08:50,190
ni trovos kion ni serĉas.

200
00:08:50,190 --> 00:08:52,150
En ĉiuj antaŭaj
ekzemploj sur duuma serĉo

201
00:08:52,150 --> 00:08:55,489
ni ĵus trapasis, se ni havus
estis serĉante la elementon 15,

202
00:08:55,489 --> 00:08:57,030
ni trovis ke tuj.

203
00:08:57,030 --> 00:08:58,321
Tio estis ĉe la komenco.

204
00:08:58,321 --> 00:09:01,200
Tio estis la mezpunkto de
la unua provo ĉe escisión

205
00:09:01,200 --> 00:09:03,950
de divido en duuma serĉo.

206
00:09:03,950 --> 00:09:06,350
>> Kaj tiel en la plej malbona
kazo, duuma serĉo kuras

207
00:09:06,350 --> 00:09:11,580
en log n, kio estas substance bona
ol lineara serĉo, en la plej malbona kazo.

208
00:09:11,580 --> 00:09:16,210
En la plej bona kazo, duuma
serĉo kuras en omega de 1.

209
00:09:16,210 --> 00:09:18,990
Do duuma serĉo estas multe
bona ol lineara serĉo,

210
00:09:18,990 --> 00:09:23,270
sed vi devas trakti kun la procezo de
ordigado via tabelo unue antaŭ vi povas

211
00:09:23,270 --> 00:09:26,140
utiligi la povon de duuma serĉo.

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

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

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