1
00:00:00,000 --> 00:00:03,346
>> [MUSIC SPILLE]

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

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

4
00:00:06,220 --> 00:00:08,140
Så binære søk er en
algoritme vi kan bruke

5
00:00:08,140 --> 00:00:10,530
å finne et element inne i en matrise.

6
00:00:10,530 --> 00:00:14,710
I motsetning til lineær søk, det krever en
særvilkår bli møtt på forhånd,

7
00:00:14,710 --> 00:00:19,020
men det er så mye mer effektiv hvis
denne tilstand er faktisk oppfylt.

8
00:00:19,020 --> 00:00:20,470
>> Så hva er ideen her?

9
00:00:20,470 --> 00:00:21,780
det er splitt og hersk.

10
00:00:21,780 --> 00:00:25,100
Vi ønsker å redusere størrelsen på
søkeområdet ved halv hver gang

11
00:00:25,100 --> 00:00:27,240
for å finne et mål nummer.

12
00:00:27,240 --> 00:00:29,520
Det er her at betingelsen
kommer inn i bildet, though.

13
00:00:29,520 --> 00:00:32,740
Vi kan bare utnytte kraften i
å eliminere halvparten av elementene

14
00:00:32,740 --> 00:00:36,070
uten å se på
dem dersom matrisen er sortert.

15
00:00:36,070 --> 00:00:39,200
>> Hvis det er en komplett blanding opp,
Vi kan ikke bare ut av hånden

16
00:00:39,200 --> 00:00:42,870
forkaste halvparten av elementene, fordi
vi vet ikke hva vi skal kastes.

17
00:00:42,870 --> 00:00:45,624
Men dersom matrisen sorteres,
vi kan gjøre det, fordi vi

18
00:00:45,624 --> 00:00:48,040
vet at alt til
igjen av hvor vi for tiden er

19
00:00:48,040 --> 00:00:50,500
må være lavere enn den
verdien vi er nå på.

20
00:00:50,500 --> 00:00:52,300
Og alt til
høyre for der vi er

21
00:00:52,300 --> 00:00:55,040
må være større enn verdien
vi for tiden ser på.

22
00:00:55,040 --> 00:00:58,710
>> Så hva er pseudo
trinn for binære søk?

23
00:00:58,710 --> 00:01:02,310
Vi gjentar denne prosessen til
matrise eller som vi går gjennom,

24
00:01:02,310 --> 00:01:07,740
sub arrays, mindre biter av
den opprinnelige matrisen, er av størrelse 0.

25
00:01:07,740 --> 00:01:10,960
Beregne midtpunktet
av den aktuelle under matrisen.

26
00:01:10,960 --> 00:01:14,460
>> Hvis verdien du leter etter er en
i det element i matrisen, stopp.

27
00:01:14,460 --> 00:01:15,030
Du fant den.

28
00:01:15,030 --> 00:01:16,550
Det er flott.

29
00:01:16,550 --> 00:01:19,610
Ellers, hvis målet er
mindre enn hva som står på midten,

30
00:01:19,610 --> 00:01:23,430
så hvis verdien vi leter
for er lavere enn det vi ser,

31
00:01:23,430 --> 00:01:26,780
gjenta denne prosessen på nytt, men
endre sluttpunkt, i stedet

32
00:01:26,780 --> 00:01:29,300
av å være den opprinnelige
full hel rekke,

33
00:01:29,300 --> 00:01:34,110
å være like til venstre
hvor vi bare så.

34
00:01:34,110 --> 00:01:38,940
>> Vi visste at midten var for høy,
eller målet var mindre enn i midten

35
00:01:38,940 --> 00:01:42,210
og slik at det må foreligge, hvis det
eksisterer i det hele tatt i matrisen,

36
00:01:42,210 --> 00:01:44,660
et sted til venstre for midtpunktet.

37
00:01:44,660 --> 00:01:48,120
Og så vil vi sette matrisen
Beliggenheten like til venstre

38
00:01:48,120 --> 00:01:51,145
fra midtpunktet som den nye målpunkt.

39
00:01:51,145 --> 00:01:53,770
Omvendt, hvis målet ligger
større enn hva som står på midten,

40
00:01:53,770 --> 00:01:55,750
vi gjøre akkurat det samme
prosessen, men i stedet vi

41
00:01:55,750 --> 00:01:59,520
endre startpunktet for å være
like til høyre for midtpunktet

42
00:01:59,520 --> 00:02:00,680
vi bare beregnet.

43
00:02:00,680 --> 00:02:03,220
Og så begynner vi prosessen på nytt.

44
00:02:03,220 --> 00:02:05,220
>> La oss visualisere dette, OK?

45
00:02:05,220 --> 00:02:08,620
Så det er mye som skjer og på her,
men her er et utvalg av de 15 elementene.

46
00:02:08,620 --> 00:02:11,400
Og vi kommer til å være å holde styr
for en mye mer ting denne gangen.

47
00:02:11,400 --> 00:02:13,870
Så i lineær søk, var vi
bare bry seg om et mål.

48
00:02:13,870 --> 00:02:15,869
Men denne gangen ønsker vi å
bryr seg om hvor vi er

49
00:02:15,869 --> 00:02:18,480
begynner å se hvor
stopper vi ser,

50
00:02:18,480 --> 00:02:21,876
og hva som er midtpunktet
av den gjeldende matrisen.

51
00:02:21,876 --> 00:02:23,250
Så her går vi med binære søk.

52
00:02:23,250 --> 00:02:25,290
Vi er ganske mye godt å gå, ikke sant?

53
00:02:25,290 --> 00:02:28,650
Jeg bare kommer til å sette ned
Nedenfor her et sett av indekser.

54
00:02:28,650 --> 00:02:32,430
Dette er i utgangspunktet akkurat det elementet
av tabellen vi snakker om.

55
00:02:32,430 --> 00:02:34,500
Med lineær søk, vi
omsorg, ettersom vi

56
00:02:34,500 --> 00:02:36,800
trenger å vite hvor mange
elementer vi gjentar løpet,

57
00:02:36,800 --> 00:02:40,010
men vi ikke egentlig bryr seg hva
element vi for tiden ser på.

58
00:02:40,010 --> 00:02:41,014
I binær søk, gjør vi.

59
00:02:41,014 --> 00:02:42,930
Og så de er bare
der som en liten guide.

60
00:02:42,930 --> 00:02:44,910
>> Så vi kan begynne, ikke sant?

61
00:02:44,910 --> 00:02:46,240
Vel, ikke helt.

62
00:02:46,240 --> 00:02:48,160
Husk hva jeg sa
om binære søk?

63
00:02:48,160 --> 00:02:50,955
Vi kan ikke gjøre det på en
usortert array eller annet,

64
00:02:50,955 --> 00:02:55,820
vi er ikke garantere at
visse elementer eller verdier ikke er

65
00:02:55,820 --> 00:02:57,650
utilsiktet
forkastes når vi bare

66
00:02:57,650 --> 00:02:59,920
velger å ignorere halvdel av tabellen.

67
00:02:59,920 --> 00:03:02,574
>> Så går man med binære søk
er at du må ha en sortert array.

68
00:03:02,574 --> 00:03:05,240
Og du kan bruke noen av sorterings
algoritmer vi har snakket om

69
00:03:05,240 --> 00:03:06,700
å få deg til den posisjonen.

70
00:03:06,700 --> 00:03:10,370
Så nå er vi i en posisjon der
vi kan utføre binære søk.

71
00:03:10,370 --> 00:03:12,560
>> Så la oss gjenta prosessen
trinn for trinn og holde

72
00:03:12,560 --> 00:03:14,830
oversikt over hva som skjer mens vi går.

73
00:03:14,830 --> 00:03:17,980
Så det første vi må gjøre er å beregne
midtpunktet av den gjeldende matrisen.

74
00:03:17,980 --> 00:03:20,620
Vel, vi vil si at vi er først og fremst
alle, på jakt etter verdien 19.

75
00:03:20,620 --> 00:03:22,290
Vi prøver å finne nummeret 19.

76
00:03:22,290 --> 00:03:25,380
Den første del av denne
matrise er plassert ved indeks null,

77
00:03:25,380 --> 00:03:28,880
og den siste del av denne
matrise ligger ved indeks 14.

78
00:03:28,880 --> 00:03:31,430
Og så skal vi kalle dem start og slutt.

79
00:03:31,430 --> 00:03:35,387
>> Så vi beregne midtpunktet av
tilsetning av 0 pluss 14 dividert med 2;

80
00:03:35,387 --> 00:03:36,720
ganske grei midtpunktet.

81
00:03:36,720 --> 00:03:40,190
Og vi kan si at
midtpunktet er nå 7.

82
00:03:40,190 --> 00:03:43,370
Så er 15 det vi leter etter?

83
00:03:43,370 --> 00:03:43,940
Nei det er det ikke.

84
00:03:43,940 --> 00:03:45,270
Vi leter etter 19.

85
00:03:45,270 --> 00:03:49,400
Men vi vet at 19 er større
enn hva vi fant på midten.

86
00:03:49,400 --> 00:03:52,470
>> Så det vi kan gjøre er å
endre startpunktet

87
00:03:52,470 --> 00:03:57,280
å være akkurat til høyre for
midtpunkt, og gjenta prosessen på nytt.

88
00:03:57,280 --> 00:04:01,690
Og når vi gjør det, har vi nå si
nytt startpunkt er matrise plassering 8.

89
00:04:01,690 --> 00:04:07,220
Det vi har effektivt gjort er
ignorert alt til venstre for 15.

90
00:04:07,220 --> 00:04:09,570
Vi har fjernet halvparten
av problemet, og nå,

91
00:04:09,570 --> 00:04:13,510
i stedet for å måtte søke
over 15 elementer i vår rekke,

92
00:04:13,510 --> 00:04:15,610
vi bare nødt til å søke i 7.

93
00:04:15,610 --> 00:04:17,706
Så 8 er den nye startpunktet.

94
00:04:17,706 --> 00:04:19,600
14 er fremdeles endepunktet.

95
00:04:19,600 --> 00:04:21,430
>> Og nå går vi over denne igjen.

96
00:04:21,430 --> 00:04:22,810
Vi beregner den nye midtpunktet.

97
00:04:22,810 --> 00:04:27,130
8 pluss 14 er 22, delt på to er 11.

98
00:04:27,130 --> 00:04:28,660
Er det dette vi leter etter?

99
00:04:28,660 --> 00:04:30,110
Nei det er det ikke.

100
00:04:30,110 --> 00:04:32,930
Vi leter etter en verdi som er
mindre enn hva vi fant.

101
00:04:32,930 --> 00:04:34,721
Så vi kommer til å gjenta
prosessen på nytt.

102
00:04:34,721 --> 00:04:38,280
Vi kommer til å endre endepunktet til
være like til venstre for midtpunktet.

103
00:04:38,280 --> 00:04:41,800
Så den nye endepunktet blir 10.

104
00:04:41,800 --> 00:04:44,780
Og nå, det er den eneste delen av
matrisen vi må sortere gjennom.

105
00:04:44,780 --> 00:04:48,460
Så vi har nå eliminert
12 av de 15 elementene.

106
00:04:48,460 --> 00:04:51,550
Vi vet at hvis 19
foreligger i matrisen, det

107
00:04:51,550 --> 00:04:57,210
må finnes et sted mellom element
nummer åtte og element nummer 10.

108
00:04:57,210 --> 00:04:59,400
>> Så vi beregne den nye midtpunktet igjen.

109
00:04:59,400 --> 00:05:02,900
8 pluss 10 er 18, dividert med 2 er 9.

110
00:05:02,900 --> 00:05:05,074
Og i dette tilfellet, se den
Målet er på midten.

111
00:05:05,074 --> 00:05:06,740
Vi fant akkurat det vi leter etter.

112
00:05:06,740 --> 00:05:07,780
Vi kan stoppe.

113
00:05:07,780 --> 00:05:10,561
Vi fullført
et binært søk.

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

115
00:05:11,060 --> 00:05:13,930
Så vi vet denne algoritmen
fungerer hvis målet er

116
00:05:13,930 --> 00:05:16,070
et eller annet sted inne i matrisen.

117
00:05:16,070 --> 00:05:19,060
Betyr denne algoritmen arbeid hvis
målet ikke er i matrisen?

118
00:05:19,060 --> 00:05:20,810
Vel, la oss starte det
igjen, og denne gangen

119
00:05:20,810 --> 00:05:23,380
la oss se for elementet
16, som visuelt kan vi se

120
00:05:23,380 --> 00:05:25,620
finnes ikke noe sted i matrisen.

121
00:05:25,620 --> 00:05:27,110
>> Startpunktet er igjen 0.

122
00:05:27,110 --> 00:05:28,590
Endepunktet er 14 igjen.

123
00:05:28,590 --> 00:05:32,490
De er indeksene i første og
siste elementer av den fullstendige matrise.

124
00:05:32,490 --> 00:05:36,057
Og vi vil gå gjennom prosessen vi bare
gikk gjennom på nytt, prøver å finne 16,

125
00:05:36,057 --> 00:05:39,140
selv om visuelt, kan vi allerede
fortelle at det ikke kommer til å være der.

126
00:05:39,140 --> 00:05:43,450
Vi ønsker bare å sørge for denne algoritmen
vil faktisk fortsatt arbeid på en eller annen måte

127
00:05:43,450 --> 00:05:46,310
og ikke bare la oss
fast i en uendelig loop.

128
00:05:46,310 --> 00:05:48,190
>> Så hva er det skritt først?

129
00:05:48,190 --> 00:05:50,230
Beregne midtpunktet
av den gjeldende matrisen.

130
00:05:50,230 --> 00:05:52,790
Hva er midtpunktet
av den gjeldende matrisen?

131
00:05:52,790 --> 00:05:54,410
Vel, det er syv, ikke sant?

132
00:05:54,410 --> 00:05:57,560
14 pluss 0 dividert med 2 er syv.

133
00:05:57,560 --> 00:05:59,280
Er 15 det vi leter etter?

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

135
00:05:59,780 --> 00:06:02,930
Det er ganske nær, men vi ser
til en verdi litt større enn det.

136
00:06:02,930 --> 00:06:06,310
>> Så vi vet at det kommer til å
være noe til venstre for 15.

137
00:06:06,310 --> 00:06:08,540
Målet er større enn
hva som er i midtpunktet.

138
00:06:08,540 --> 00:06:12,450
Og så setter vi det nye startpunktet til
være akkurat til høyre for midten.

139
00:06:12,450 --> 00:06:16,130
Midtpunktet er for tiden 7, så
la oss si den nye startpunktet er åtte.

140
00:06:16,130 --> 00:06:18,130
Og det vi har effektivt
gjort på nytt blir ignorert

141
00:06:18,130 --> 00:06:21,150
hele venstre halvdel av matrisen.

142
00:06:21,150 --> 00:06:23,750
>> Nå, vi gjenta
behandle en gang til.

143
00:06:23,750 --> 00:06:24,910
Beregn den nye midtpunktet.

144
00:06:24,910 --> 00:06:29,350
8 pluss 14 er 22, delt på to er 11.

145
00:06:29,350 --> 00:06:31,060
Er 23 det vi leter etter?

146
00:06:31,060 --> 00:06:31,870
Dessverre ikke.

147
00:06:31,870 --> 00:06:34,930
Vi leter etter en verdi
som er mindre enn 23.

148
00:06:34,930 --> 00:06:37,850
Og så i dette tilfellet, skal vi
å endre sluttpunktet for å være like

149
00:06:37,850 --> 00:06:40,035
til venstre for det gjeldende midtpunktet.

150
00:06:40,035 --> 00:06:43,440
Den nåværende punktet er 11, og
så vi vil sette ny sluttpunktet

151
00:06:43,440 --> 00:06:46,980
til neste gang vi går
gjennom denne prosessen for å 10.

152
00:06:46,980 --> 00:06:48,660
>> Igjen, vi går gjennom prosessen på nytt.

153
00:06:48,660 --> 00:06:49,640
Beregne midtpunktet.

154
00:06:49,640 --> 00:06:53,100
8 pluss 10 dividert med 2 er 9.

155
00:06:53,100 --> 00:06:54,750
Er 19 det vi leter etter?

156
00:06:54,750 --> 00:06:55,500
Dessverre ikke.

157
00:06:55,500 --> 00:06:58,050
Vi er fortsatt på jakt etter
et tall som er mindre enn det.

158
00:06:58,050 --> 00:07:02,060
Så vi kommer til å endre sluttpunktet denne gangen
å være like til venstre for midtpunktet.

159
00:07:02,060 --> 00:07:05,532
Midtpunktet er for tiden 9,
slik at endepunktet vil være åtte.

160
00:07:05,532 --> 00:07:07,920
Og nå er vi bare ute
ved et enkelt element array.

161
00:07:07,920 --> 00:07:10,250
>> Hva er midtpunktet i denne tabellen?

162
00:07:10,250 --> 00:07:13,459
Vel, den starter på 8, det
slutter ved 8, er midtpunktet 8.

163
00:07:13,459 --> 00:07:14,750
Er det det vi leter etter?

164
00:07:14,750 --> 00:07:16,339
Er vi på jakt etter 17?

165
00:07:16,339 --> 00:07:17,380
Nei, vi leter etter 16.

166
00:07:17,380 --> 00:07:20,160
Så hvis det finnes i tabellen,
det må finnes et sted

167
00:07:20,160 --> 00:07:21,935
til venstre for der vi er nå.

168
00:07:21,935 --> 00:07:23,060
Så hva skal vi gjøre?

169
00:07:23,060 --> 00:07:26,610
Vel, vi vil sette sluttpunktet for å være like
til venstre for det gjeldende midtpunktet.

170
00:07:26,610 --> 00:07:29,055
Så vi kommer til å endre sluttpunktet til 7.

171
00:07:29,055 --> 00:07:32,120
Ser du hva som nettopp
skjedd her, da?

172
00:07:32,120 --> 00:07:33,370
Slå opp her nå.

173
00:07:33,370 --> 00:07:35,970
>> Start er nå større enn slutten.

174
00:07:35,970 --> 00:07:39,620
Vel, de to endene
av vår rekke har krysset,

175
00:07:39,620 --> 00:07:42,252
og startpunktet er
nå etter sluttpunktet.

176
00:07:42,252 --> 00:07:43,960
Vel, gjør det ikke
gjøre noe fornuftig, ikke sant?

177
00:07:43,960 --> 00:07:47,960
Så nå, hva vi kan si er at vi
har en sub utvalg av størrelse 0.

178
00:07:47,960 --> 00:07:50,110
Og når vi er kommet til
dette punktet, kan vi nå

179
00:07:50,110 --> 00:07:53,940
garantere at element 16
finnes ikke i tabellen,

180
00:07:53,940 --> 00:07:56,280
fordi startpunktet
og sluttpunkt har krysset.

181
00:07:56,280 --> 00:07:58,340
Og så det er ikke der.

182
00:07:58,340 --> 00:08:01,340
Nå, merker at dette er noe
annerledes enn startpunkt og slutt

183
00:08:01,340 --> 00:08:02,900
punkt er den samme.

184
00:08:02,900 --> 00:08:05,030
Hvis vi hadde vært ute
til 17, ville det ha

185
00:08:05,030 --> 00:08:08,870
vært i matrisen, og startpunktet
og sluttpunkt for den siste iterasjon

186
00:08:08,870 --> 00:08:11,820
før disse punktene krysset,
vi ville ha funnet 17 der.

187
00:08:11,820 --> 00:08:15,510
Det er bare når de krysser at vi kan
garanterer at elementet ikke

188
00:08:15,510 --> 00:08:17,180
finnes i tabellen.

189
00:08:17,180 --> 00:08:20,260
>> Så la oss ta en mye mindre
trinn enn lineær søk.

190
00:08:20,260 --> 00:08:23,250
I verste fall, hadde vi
å splitte opp en liste med n elementer

191
00:08:23,250 --> 00:08:27,770
gjentatte ganger i to for å finne målet,
enten ved at målelementet

192
00:08:27,770 --> 00:08:33,110
vil være et sted i den siste
divisjon, eller det ikke eksisterer i det hele tatt.

193
00:08:33,110 --> 00:08:37,830
Så i verste fall må vi
splitte opp array-- vet du det?

194
00:08:37,830 --> 00:08:40,510
Logg n ganger; vi
må kutte problemet

195
00:08:40,510 --> 00:08:42,610
i halv et visst antall ganger.

196
00:08:42,610 --> 00:08:45,160
At antall ganger er log n.

197
00:08:45,160 --> 00:08:46,510
>> Hva er den best case scenario?

198
00:08:46,510 --> 00:08:48,899
Vel, første gang vi
beregne midtpunktet,

199
00:08:48,899 --> 00:08:50,190
vi finner det vi leter etter.

200
00:08:50,190 --> 00:08:52,150
I alle de tidligere
eksempler på binære søk

201
00:08:52,150 --> 00:08:55,489
Vi har nettopp gått over, hvis vi hadde
vært på jakt etter elementet 15,

202
00:08:55,489 --> 00:08:57,030
vi ville ha funnet det umiddelbart.

203
00:08:57,030 --> 00:08:58,321
Det var helt i begynnelsen.

204
00:08:58,321 --> 00:09:01,200
Det var midtpunktet av
det første forsøket på en delt

205
00:09:01,200 --> 00:09:03,950
av en avdeling i binært søk.

206
00:09:03,950 --> 00:09:06,350
>> Og så i verste
tilfellet går binære søk

207
00:09:06,350 --> 00:09:11,580
i log n, som er vesentlig bedre
enn lineær søk, i verste fall.

208
00:09:11,580 --> 00:09:16,210
I beste fall, binære
søk kjører i omega for en.

209
00:09:16,210 --> 00:09:18,990
Så binære søk er mye
bedre enn lineær søk,

210
00:09:18,990 --> 00:09:23,270
men du har å forholde seg til prosessen med
sortering array først før du kan

211
00:09:23,270 --> 00:09:26,140
utnytte kraften i binære søk.

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

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

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