1
00:00:00,000 --> 00:00:03,346
>> [TÓNLIST spila]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Allt í lagi.

4
00:00:06,220 --> 00:00:08,140
Svo er tvöfaldur leita að
algrím við getum notað

5
00:00:08,140 --> 00:00:10,530
að finna stak inni fylki.

6
00:00:10,530 --> 00:00:14,710
Ólíkt línuleg leit, það krefst
sérstök skilyrði að vera uppfyllt fyrirfram,

7
00:00:14,710 --> 00:00:19,020
en það er svo miklu meira duglegur ef
að ástand er í raun uppfyllt.

8
00:00:19,020 --> 00:00:20,470
>> Svo er það hugmynd hér?

9
00:00:20,470 --> 00:00:21,780
það er gjá og sigra.

10
00:00:21,780 --> 00:00:25,100
Við viljum draga úr stærð
leitarsvæðinu um helming í hvert skipti

11
00:00:25,100 --> 00:00:27,240
í því skyni að finna miða númer.

12
00:00:27,240 --> 00:00:29,520
Þetta er þar sem það skilyrði
kemur inn í leik, þó.

13
00:00:29,520 --> 00:00:32,740
Við getum aðeins áhrif á afl
útrýming helmingur af þeim þáttum

14
00:00:32,740 --> 00:00:36,070
án þess þó að horfa á
þá ef array er raðað.

15
00:00:36,070 --> 00:00:39,200
>> Ef það er heill blanda upp,
við getum ekki bara úr böndunum

16
00:00:39,200 --> 00:00:42,870
henda helmingur af þeim þáttum, vegna
við vitum ekki hvað við erum að fleygja.

17
00:00:42,870 --> 00:00:45,624
En ef array er raðað,
við getum gert það, vegna þess að við

18
00:00:45,624 --> 00:00:48,040
vita að allt til
vinstri á hvar við erum núna

19
00:00:48,040 --> 00:00:50,500
verður að vera lægra en
gildi við erum nú á.

20
00:00:50,500 --> 00:00:52,300
Og allt til
rétt um hvar við erum

21
00:00:52,300 --> 00:00:55,040
verður að vera hærri en gildið
við erum nú að horfa á.

22
00:00:55,040 --> 00:00:58,710
>> Svo er það sauðakóðanum
skref fyrir tvöfaldur leit?

23
00:00:58,710 --> 00:01:02,310
Við endurtaka þetta ferli þar til
array eða, eins og við halda áfram í gegnum,

24
00:01:02,310 --> 00:01:07,740
undir fylki, smærri stykki af
upprunalega array, af stærð 0.

25
00:01:07,740 --> 00:01:10,960
Reikna miðpunkt
af núverandi undir fylkisins.

26
00:01:10,960 --> 00:01:14,460
>> Ef gildið sem þú ert að leita að er
í því frumefni af the array, hætta.

27
00:01:14,460 --> 00:01:15,030
Þú fannst það.

28
00:01:15,030 --> 00:01:16,550
Það er frábært.

29
00:01:16,550 --> 00:01:19,610
Annars, ef miðað er
minna en það sem er á miðju,

30
00:01:19,610 --> 00:01:23,430
þannig að ef verðmæti við erum að leita
fyrir er lægra en það sem við sjáum,

31
00:01:23,430 --> 00:01:26,780
endurtaka þetta ferli aftur, en
breyta endastað stað

32
00:01:26,780 --> 00:01:29,300
af því að vera upprunalega
ljúka fullt fjölbreytta,

33
00:01:29,300 --> 00:01:34,110
að vera bara til vinstri
þar sem við horfði bara.

34
00:01:34,110 --> 00:01:38,940
>> Við vissum að miðja var of hár,
eða miða var minna en miðju,

35
00:01:38,940 --> 00:01:42,210
og svo það verður að vera til, ef það
er til á öllum í fylkinu,

36
00:01:42,210 --> 00:01:44,660
einhvers staðar vinstra megin við miðpunkt.

37
00:01:44,660 --> 00:01:48,120
Og svo við munum stilla array
staðsetningu bara til vinstri

38
00:01:48,120 --> 00:01:51,145
á miðju sem nýr endir benda.

39
00:01:51,145 --> 00:01:53,770
Hins vegar ef miðað er
meiri en það er á miðju,

40
00:01:53,770 --> 00:01:55,750
við gerum nákvæmlega sama
ferli, en í staðinn erum við

41
00:01:55,750 --> 00:01:59,520
breyta upphafsstað að vera
bara til hægri miðpunkt

42
00:01:59,520 --> 00:02:00,680
við reiknað bara.

43
00:02:00,680 --> 00:02:03,220
Og þá byrjum við ferlið aftur.

44
00:02:03,220 --> 00:02:05,220
>> Skulum sjón þetta í lagi?

45
00:02:05,220 --> 00:02:08,620
Svo er það mikið að fara og hér,
en hér er fylki af 15 þáttum.

46
00:02:08,620 --> 00:02:11,400
Og við erum að fara að vera að halda utan
af a einhver fjöldi fleiri efni í þetta sinn.

47
00:02:11,400 --> 00:02:13,870
Svo í línuleg leit, við vorum
bara umhyggju miða.

48
00:02:13,870 --> 00:02:15,869
En í þetta sinn við viljum
sama um hvar erum við

49
00:02:15,869 --> 00:02:18,480
farin að líta, þar
við erum hætt að leita,

50
00:02:18,480 --> 00:02:21,876
og hvað er miðpunkt
af núverandi array.

51
00:02:21,876 --> 00:02:23,250
Svo hér við fara með tvöfaldur leit.

52
00:02:23,250 --> 00:02:25,290
Við erum nokkuð mikið gott að fara, ekki satt?

53
00:02:25,290 --> 00:02:28,650
Ég ætla bara að fara að setja niður
neðan hér sett af vísitölum.

54
00:02:28,650 --> 00:02:32,430
Þetta er í rauninni bara það sem þáttur
fylkisins við erum að tala um.

55
00:02:32,430 --> 00:02:34,500
Með línuleg leit við
umönnun, að því leyti sem vér

56
00:02:34,500 --> 00:02:36,800
þarf að vita hversu margir
þættir sem við erum iterating yfir,

57
00:02:36,800 --> 00:02:40,010
en við gerum ekki raunverulega sama hvað
þáttur við erum nú að horfa á.

58
00:02:40,010 --> 00:02:41,014
Í tvöfaldur leit, gera við.

59
00:02:41,014 --> 00:02:42,930
Og svo þeir eru bara
það sem smá leiðbeiningar.

60
00:02:42,930 --> 00:02:44,910
>> Svo við getum byrjað, ekki satt?

61
00:02:44,910 --> 00:02:46,240
Jæja, ekki alveg.

62
00:02:46,240 --> 00:02:48,160
Mundu það sem ég sagði
um tvöfaldur leit?

63
00:02:48,160 --> 00:02:50,955
Við getum ekki gert það á
Óflokkaður array eða annað,

64
00:02:50,955 --> 00:02:55,820
við erum ekki að tryggja að
ákveðnir þættir eða gildi ekki

65
00:02:55,820 --> 00:02:57,650
vera tilviljun
hent þegar við bara

66
00:02:57,650 --> 00:02:59,920
ákveðið að hunsa helmingur fylkisins.

67
00:02:59,920 --> 00:03:02,574
>> Svo stíga einn með tvöfaldur leit
er þú verður að hafa flokkað array.

68
00:03:02,574 --> 00:03:05,240
Og þú getur notað eitthvað af flokkun
reiknirit sem við höfum talað um

69
00:03:05,240 --> 00:03:06,700
til að fá þig til að staða.

70
00:03:06,700 --> 00:03:10,370
Svo nú erum við í þeirri stöðu að
við getum gert tvöfaldur leit.

71
00:03:10,370 --> 00:03:12,560
>> Svo skulum endurtaka ferlið
skref fyrir skref og halda

72
00:03:12,560 --> 00:03:14,830
utan um hvað er að gerast sem við förum.

73
00:03:14,830 --> 00:03:17,980
Svo fyrsta sem við þurfum að gera er að reikna
miðpunkt núverandi array.

74
00:03:17,980 --> 00:03:20,620
Jæja, munum við segja að við erum fyrst af
allt, leita að verðmæti 19.

75
00:03:20,620 --> 00:03:22,290
Við erum að reyna að finna númerið 19.

76
00:03:22,290 --> 00:03:25,380
Fyrsti þáttur af þessu
array er staðsett á vísitölu núll,

77
00:03:25,380 --> 00:03:28,880
og síðast þáttur af þessu
array er staðsett á vísitölu 14.

78
00:03:28,880 --> 00:03:31,430
Og svo við munum kalla þá upphaf og lok.

79
00:03:31,430 --> 00:03:35,387
>> Svo við reiknum miðpunkt með
bæta 0 plús 14 deilt með 2;

80
00:03:35,387 --> 00:03:36,720
nokkuð augljóst miðpunkt.

81
00:03:36,720 --> 00:03:40,190
Og við getum sagt að
miðpunkt er nú 7.

82
00:03:40,190 --> 00:03:43,370
Svo er 15 það sem við erum að leita að?

83
00:03:43,370 --> 00:03:43,940
Nei það er ekki.

84
00:03:43,940 --> 00:03:45,270
Við erum að leita að 19.

85
00:03:45,270 --> 00:03:49,400
En við vitum að 19 er meiri
en það sem við fundum á miðjunni.

86
00:03:49,400 --> 00:03:52,470
>> Svo er það sem við getum gert
breyta upphafsstað

87
00:03:52,470 --> 00:03:57,280
að vera bara til hægri af
miðpunkt, og endurtaka ferlið aftur.

88
00:03:57,280 --> 00:04:01,690
Og þegar við gerum það, segjum við nú
nýtt upphaf liður er array staðsetningu 8.

89
00:04:01,690 --> 00:04:07,220
Það sem við höfum í raun gert er
hunsað allt vinstra megin við 15.

90
00:04:07,220 --> 00:04:09,570
Við höfum eytt helmingi
af vandamálinu, og nú,

91
00:04:09,570 --> 00:04:13,510
í stað þess að þurfa að leita
yfir 15 þættir í fylking okkar,

92
00:04:13,510 --> 00:04:15,610
höfum við aðeins að leita á 7.

93
00:04:15,610 --> 00:04:17,706
Svo er 8 nýja upphafsstað.

94
00:04:17,706 --> 00:04:19,600
14 er enn endapunkturinn.

95
00:04:19,600 --> 00:04:21,430
>> Og nú förum við yfir þetta aftur.

96
00:04:21,430 --> 00:04:22,810
Við reikna nýja miðpunkt.

97
00:04:22,810 --> 00:04:27,130
8 plús 14 er 22, deilt með 2 er 11.

98
00:04:27,130 --> 00:04:28,660
Er þetta það sem við erum að leita að?

99
00:04:28,660 --> 00:04:30,110
Nei það er ekki.

100
00:04:30,110 --> 00:04:32,930
Við erum að leita fyrir gildi sem er
minna en það sem við fundum bara.

101
00:04:32,930 --> 00:04:34,721
Þannig að við erum að fara að endurtaka
ferlið aftur.

102
00:04:34,721 --> 00:04:38,280
Við erum að fara að breyta endastað til
bara vinstra megin við miðpunkt.

103
00:04:38,280 --> 00:04:41,800
Svo nýja endapunkturinn verður 10.

104
00:04:41,800 --> 00:04:44,780
Og nú, það er bara hluti af
array við verðum að raða í gegnum.

105
00:04:44,780 --> 00:04:48,460
Þannig að við höfum nú eytt
12 af 15 þáttum.

106
00:04:48,460 --> 00:04:51,550
Við vitum að ef 19
er í fylkinu, það

107
00:04:51,550 --> 00:04:57,210
þarf að liggja einhvers staðar á milli frumefni
númer 8 og frumefni númer 10.

108
00:04:57,210 --> 00:04:59,400
>> Svo við reiknum nýja miðpunkt aftur.

109
00:04:59,400 --> 00:05:02,900
8 plús 10 er 18, deilt með 2 er 9.

110
00:05:02,900 --> 00:05:05,074
Og í þessu tilfelli, líta, því
miða er á miðjunni.

111
00:05:05,074 --> 00:05:06,740
Við fundum einmitt það sem við erum að leita að.

112
00:05:06,740 --> 00:05:07,780
Við getum hætt.

113
00:05:07,780 --> 00:05:10,561
Við lokið
tvöfaldur leit.

114
00:05:10,561 --> 00:05:11,060
Allt í lagi.

115
00:05:11,060 --> 00:05:13,930
Þannig að við vitum þetta reiknirit
virkar ef miðað er

116
00:05:13,930 --> 00:05:16,070
einhvers staðar inni í fylkinu.

117
00:05:16,070 --> 00:05:19,060
Er þetta reiknirit virka ef
markmiðið er ekki í fylkinu?

118
00:05:19,060 --> 00:05:20,810
Jæja, við skulum byrja það
aftur, og að þessu sinni,

119
00:05:20,810 --> 00:05:23,380
við skulum líta á frumefni
16, sem sjónrænt við getum séð

120
00:05:23,380 --> 00:05:25,620
er ekki til staðar í fylkinu.

121
00:05:25,620 --> 00:05:27,110
>> Upphaf málsins er aftur 0.

122
00:05:27,110 --> 00:05:28,590
The endir benda er aftur 14.

123
00:05:28,590 --> 00:05:32,490
Þeir eru vísitala fyrst og
Síðustu þættir heill fylkisins.

124
00:05:32,490 --> 00:05:36,057
Og við munum fara í gegnum ferlið við bara
fór í gegnum aftur, reyna að finna 16,

125
00:05:36,057 --> 00:05:39,140
jafnvel þó sjónrænt, getum við nú þegar
segja að það er ekki að fara að vera þar.

126
00:05:39,140 --> 00:05:43,450
Við viljum bara að ganga úr skugga um þetta reiknirit
mun í raun enn að vinna á einhvern hátt

127
00:05:43,450 --> 00:05:46,310
og ekki bara láta okkur
fastur í óendanlega lykkju.

128
00:05:46,310 --> 00:05:48,190
>> Svo er það skref fyrst?

129
00:05:48,190 --> 00:05:50,230
Reikna miðpunkt
af núverandi array.

130
00:05:50,230 --> 00:05:52,790
Hvað er miðpunktur
núverandi array?

131
00:05:52,790 --> 00:05:54,410
Jæja, það er 7, ekki satt?

132
00:05:54,410 --> 00:05:57,560
14 plús 0 deilt með 2 er 7.

133
00:05:57,560 --> 00:05:59,280
Er 15 það sem við erum að leita að?

134
00:05:59,280 --> 00:05:59,780
Nei

135
00:05:59,780 --> 00:06:02,930
Það er mjög nálægt, en við erum að leita
fyrir gildi örlítið stærri en það.

136
00:06:02,930 --> 00:06:06,310
>> Þannig að við vitum að það er að fara að
hvergi vinstra megin við 15.

137
00:06:06,310 --> 00:06:08,540
Útkoman er meiri en
hvað er í miðju.

138
00:06:08,540 --> 00:06:12,450
Og svo við setjum nýja upphafsstað til
vera rétt hægra megin við miðju.

139
00:06:12,450 --> 00:06:16,130
Miðpunkt er nú 7, svo
skulum segja að nýtt upphaf liður er 8.

140
00:06:16,130 --> 00:06:18,130
Og það sem við höfum í raun
gert aftur er hunsaður

141
00:06:18,130 --> 00:06:21,150
allt vinstri helminginn af fylkisins.

142
00:06:21,150 --> 00:06:23,750
>> Nú endurtaka við að
vinna einu sinni.

143
00:06:23,750 --> 00:06:24,910
Reikna nýja miðpunkt.

144
00:06:24,910 --> 00:06:29,350
8 plús 14 er 22, deilt með 2 er 11.

145
00:06:29,350 --> 00:06:31,060
Er 23 það sem við erum að leita að?

146
00:06:31,060 --> 00:06:31,870
Því miður, engin.

147
00:06:31,870 --> 00:06:34,930
Við erum að leita fyrir gildi
sem er minna en 23.

148
00:06:34,930 --> 00:06:37,850
Og svo í þessu tilfelli erum við að fara
að breyta endastað að vera bara

149
00:06:37,850 --> 00:06:40,035
vinstra megin við núverandi miðpunkt.

150
00:06:40,035 --> 00:06:43,440
Núverandi miðpunkt er 11, og
þannig að við munum setja nýja endastað

151
00:06:43,440 --> 00:06:46,980
fyrir næsta skipti sem við förum
í gegnum þetta ferli til 10.

152
00:06:46,980 --> 00:06:48,660
>> Aftur, við förum í gegnum ferlið aftur.

153
00:06:48,660 --> 00:06:49,640
Reikna miðpunkt.

154
00:06:49,640 --> 00:06:53,100
8 plús 10 deilt með 2 er 9.

155
00:06:53,100 --> 00:06:54,750
Er 19 það sem við erum að leita að?

156
00:06:54,750 --> 00:06:55,500
Því miður, engin.

157
00:06:55,500 --> 00:06:58,050
Við erum enn að leita að
a tala minna en það.

158
00:06:58,050 --> 00:07:02,060
Þannig að við munum breyta endastað þetta sinn
að vera bara vinstra megin við miðpunkt.

159
00:07:02,060 --> 00:07:05,532
Miðpunkt er nú 9,
svo endapunkturinn verður 8.

160
00:07:05,532 --> 00:07:07,920
Og nú, við erum bara að leita
á einni þáttur array.

161
00:07:07,920 --> 00:07:10,250
>> Hvað er miðpunktur þessa array?

162
00:07:10,250 --> 00:07:13,459
Jæja, það byrjar á 8, það
endar á 8, miðpunkt er 8.

163
00:07:13,459 --> 00:07:14,750
Er það það sem við erum að leita að?

164
00:07:14,750 --> 00:07:16,339
Erum við að leita að 17?

165
00:07:16,339 --> 00:07:17,380
Nei, við erum að leita fyrir 16.

166
00:07:17,380 --> 00:07:20,160
Þannig að ef það er til staðar í fylkinu,
það verður að vera til staðar

167
00:07:20,160 --> 00:07:21,935
vinstra megin við þar sem við erum nú.

168
00:07:21,935 --> 00:07:23,060
Svo hvað erum við að fara að gera?

169
00:07:23,060 --> 00:07:26,610
Jæja, munum við að ákvarða endastað að vera bara
vinstra megin við núverandi miðpunkt.

170
00:07:26,610 --> 00:07:29,055
Þannig að við munum breyta endastað til 7.

171
00:07:29,055 --> 00:07:32,120
Sérðu hvað bara
gerðist hér, þó?

172
00:07:32,120 --> 00:07:33,370
Horfðu upp hér núna.

173
00:07:33,370 --> 00:07:35,970
>> Start er nú meiri en í lok.

174
00:07:35,970 --> 00:07:39,620
Á áhrifaríkan hátt, tveir endar
af array okkar hafa yfir,

175
00:07:39,620 --> 00:07:42,252
og upphafsstað er
nú eftir endapunktur.

176
00:07:42,252 --> 00:07:43,960
Jæja, það er ekki
gera allir skilningarvit, ekki satt?

177
00:07:43,960 --> 00:07:47,960
Svo nú, hvað við getum sagt er að við
hafa undir fjölbreytta stærð 0.

178
00:07:47,960 --> 00:07:50,110
Og þegar við erum farinn að
þetta lið, getum við nú

179
00:07:50,110 --> 00:07:53,940
tryggja að sá hluti 16
er ekki til í fylkinu,

180
00:07:53,940 --> 00:07:56,280
vegna þess að byrjun
og endir benda hafa yfir.

181
00:07:56,280 --> 00:07:58,340
Og svo er það ekki þar.

182
00:07:58,340 --> 00:08:01,340
Nú, eftir að þetta er örlítið
öðruvísi en upphafsstað og enda

183
00:08:01,340 --> 00:08:02,900
benda að vera sama.

184
00:08:02,900 --> 00:08:05,030
Ef við hefðum verið að leita
í 17, það myndi hafa

185
00:08:05,030 --> 00:08:08,870
verið í fylkinu, og byrjun
og endir benda á að á síðasta endurtekning

186
00:08:08,870 --> 00:08:11,820
áður en þeir stig yfir,
við hefðum fundið 17 þar.

187
00:08:11,820 --> 00:08:15,510
Það er aðeins þegar þeir fara yfir það sem við getum
tryggja að þátturinn er ekki

188
00:08:15,510 --> 00:08:17,180
eru í fylkinu.

189
00:08:17,180 --> 00:08:20,260
>> Svo skulum taka a einhver fjöldi færri
skref en línuleg leit.

190
00:08:20,260 --> 00:08:23,250
Í versta falli, við höfðum
að skipta upp lista yfir n þætti

191
00:08:23,250 --> 00:08:27,770
ítrekað í tvennt til að finna miða,
annaðhvort vegna þess að miða þáttur

192
00:08:27,770 --> 00:08:33,110
mun vera einhvers staðar í síðasta
deild, eða það er ekki til á öllum.

193
00:08:33,110 --> 00:08:37,830
Svo í versta tilfelli, verðum við að
skipt upp í array-- veistu?

194
00:08:37,830 --> 00:08:40,510
Log n sinnum, við
þurfa að skera vandamál

195
00:08:40,510 --> 00:08:42,610
í hálfan ákveðinn fjölda skipta.

196
00:08:42,610 --> 00:08:45,160
Sem fjöldi skipta er log n.

197
00:08:45,160 --> 00:08:46,510
>> Hvað er besta falli?

198
00:08:46,510 --> 00:08:48,899
Jæja, fyrsta skipti sem við
reikna miðpunkt,

199
00:08:48,899 --> 00:08:50,190
finnum það sem við erum að leita að.

200
00:08:50,190 --> 00:08:52,150
Í öllum fyrri
dæmi um tvöfaldur leit

201
00:08:52,150 --> 00:08:55,489
við höfum bara farið yfir, ef við hefðum
verið að leita að frumefni 15,

202
00:08:55,489 --> 00:08:57,030
við hefðum komist að strax.

203
00:08:57,030 --> 00:08:58,321
Það var í upphafi.

204
00:08:58,321 --> 00:09:01,200
Það var miðpunktur
fyrsta tilraun á hættu

205
00:09:01,200 --> 00:09:03,950
af deild í tvöfaldur leit.

206
00:09:03,950 --> 00:09:06,350
>> Og svo í versta
ræða, tvöfaldur leita keyrir

207
00:09:06,350 --> 00:09:11,580
í log n, sem er talsvert betri
en línuleg leit, í versta tilfelli.

208
00:09:11,580 --> 00:09:16,210
Í besta tilfelli, tvöfaldur
Leita keyrir omega af 1.

209
00:09:16,210 --> 00:09:18,990
Svo er tvöfaldur leita mikið
betri en línuleg leit,

210
00:09:18,990 --> 00:09:23,270
en þú verður að takast á við ferli
flokkun array fyrst áður en þú getur

211
00:09:23,270 --> 00:09:26,140
áhrif á afl tvöfaldur leit.

212
00:09:26,140 --> 00:09:27,130
>> Ég er Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Þetta er CS 50.

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