1
00:00:00,000 --> 00:00:03,346
>> [Musik spiller]

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

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

4
00:00:06,220 --> 00:00:08,140
Så binær søgning er en
algoritme vi kan bruge

5
00:00:08,140 --> 00:00:10,530
at finde et element inde i et array.

6
00:00:10,530 --> 00:00:14,710
I modsætning til lineær søgning, men det kræver en
særlige betingelse være opfyldt på forhånd,

7
00:00:14,710 --> 00:00:19,020
men det er så meget mere effektiv, hvis
denne betingelse er faktisk opfyldt.

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

9
00:00:20,470 --> 00:00:21,780
det er kløft og erobre.

10
00:00:21,780 --> 00:00:25,100
Vi ønsker at reducere størrelsen af
søgeområdet med halvdelen hver gang

11
00:00:25,100 --> 00:00:27,240
med henblik på at finde en destinationsnummer.

12
00:00:27,240 --> 00:00:29,520
Det er her, denne betingelse
kommer i spil, selv om.

13
00:00:29,520 --> 00:00:32,740
Vi kan kun udnytte kraften i
fjerne halvdelen af ​​elementerne

14
00:00:32,740 --> 00:00:36,070
uden selv at se på
dem, hvis array sorteres.

15
00:00:36,070 --> 00:00:39,200
>> Hvis det er en komplet blanding op,
Vi kan ikke bare ud af hånden

16
00:00:39,200 --> 00:00:42,870
skille halvdelen af ​​elementerne, fordi
Vi ved ikke, hvad vi kassere.

17
00:00:42,870 --> 00:00:45,624
Men hvis arrayet er sorteret,
vi kan gøre det, fordi vi

18
00:00:45,624 --> 00:00:48,040
ved, at alt til
tilbage af, hvor vi i øjeblikket er

19
00:00:48,040 --> 00:00:50,500
skal være lavere end den
værdi, vi er her på.

20
00:00:50,500 --> 00:00:52,300
Og alt til
ret til, hvor vi er

21
00:00:52,300 --> 00:00:55,040
skal være større end værdien
vi i øjeblikket kigger på.

22
00:00:55,040 --> 00:00:58,710
>> Så hvad er pseudokode
trin for binær søgning?

23
00:00:58,710 --> 00:01:02,310
Vi gentager denne proces, indtil den
matrix eller, som vi fortsætte gennem,

24
00:01:02,310 --> 00:01:07,740
sub arrays, mindre stykker
den oprindelige matrix, er størrelse 0.

25
00:01:07,740 --> 00:01:10,960
Beregn midtpunktet
af den nuværende sub-array.

26
00:01:10,960 --> 00:01:14,460
>> Hvis den værdi, du leder efter
i denne del af matrixen, stop.

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

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

29
00:01:16,550 --> 00:01:19,610
Ellers, hvis målet er
mindre end, hvad der er i midten,

30
00:01:19,610 --> 00:01:23,430
så hvis den værdi, vi leder efter
for er lavere end det, vi ser,

31
00:01:23,430 --> 00:01:26,780
gentage denne proces igen, men
ændre slutpunktet, i stedet

32
00:01:26,780 --> 00:01:29,300
for at være den oprindelige
fuldføre fuld array,

33
00:01:29,300 --> 00:01:34,110
at være lige til venstre
af, hvor vi lige har set.

34
00:01:34,110 --> 00:01:38,940
>> Vi vidste, at den midterste var for høj,
eller målet var mindre end i midten,

35
00:01:38,940 --> 00:01:42,210
og det skal eksistere, hvis det
overhovedet eksisterer i arrayet,

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

37
00:01:44,660 --> 00:01:48,120
Og så vil vi sætte array
placering lige til venstre

38
00:01:48,120 --> 00:01:51,145
af midtpunktet som den nye slutpunkt.

39
00:01:51,145 --> 00:01:53,770
Omvendt, hvis målet er
større end, hvad der er i midten,

40
00:01:53,770 --> 00:01:55,750
vi gør præcis de samme
proces, men i stedet vi

41
00:01:55,750 --> 00:01:59,520
ændre startpunktet at være
lige til højre for midtpunktet

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

43
00:02:00,680 --> 00:02:03,220
Og så begynder vi processen igen.

44
00:02:03,220 --> 00:02:05,220
>> Lad os visualisere det, OK?

45
00:02:05,220 --> 00:02:08,620
Så der er en masse i gang, og her,
men her er en række af de 15 elementer.

46
00:02:08,620 --> 00:02:11,400
Og vi kommer til at holde styr
af en masse flere ting denne gang.

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

48
00:02:13,870 --> 00:02:15,869
Men denne gang vil vi
bekymrer sig om hvor er vi

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

50
00:02:18,480 --> 00:02:21,876
og hvad er midtpunktet
af den nuværende array.

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

52
00:02:23,250 --> 00:02:25,290
Vi er temmelig meget god til at gå, ikke?

53
00:02:25,290 --> 00:02:28,650
Jeg bare at sætte ned
nedenfor her et sæt af indekser.

54
00:02:28,650 --> 00:02:32,430
Dette er dybest set lige hvad element
af array, vi taler om.

55
00:02:32,430 --> 00:02:34,500
Med lineær søgning, vi
pleje, idet vi

56
00:02:34,500 --> 00:02:36,800
brug for at vide, hvor mange
elementer vi iteration løbet,

57
00:02:36,800 --> 00:02:40,010
men vi ved ikke faktisk pleje, hvad
element vi i øjeblikket kigger på.

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

59
00:02:41,014 --> 00:02:42,930
Og så dem er blot
der som en lille guide.

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

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

62
00:02:46,240 --> 00:02:48,160
Husk, hvad jeg sagde
om binær søgning?

63
00:02:48,160 --> 00:02:50,955
Vi kan ikke gøre det på en
usorteret matrix eller andet,

64
00:02:50,955 --> 00:02:55,820
vi er ikke garanti for, at den
visse elementer eller værdier ikke

65
00:02:55,820 --> 00:02:57,650
utilsigtet
kasseres, når vi blot

66
00:02:57,650 --> 00:02:59,920
beslutte at ignorere halvdelen af ​​arrayet.

67
00:02:59,920 --> 00:03:02,574
>> Så trin en med binær søgning
er du skal have et ordnet array.

68
00:03:02,574 --> 00:03:05,240
Og du kan bruge nogen af ​​sorteringen
algoritmer vi har talt om

69
00:03:05,240 --> 00:03:06,700
at få dig til denne stilling.

70
00:03:06,700 --> 00:03:10,370
Så nu er vi i en position, hvor
Vi kan udføre binær søgning.

71
00:03:10,370 --> 00:03:12,560
>> Så lad os gentage processen
trin for trin og holde

72
00:03:12,560 --> 00:03:14,830
styr på, hvad der sker, når vi går.

73
00:03:14,830 --> 00:03:17,980
Så det første, vi skal gøre, er at beregne
midtpunktet af det aktuelle array.

74
00:03:17,980 --> 00:03:20,620
Nå, vil vi sige, vi er først og
alle, på udkig efter værdien 19.

75
00:03:20,620 --> 00:03:22,290
Vi forsøger at finde nummeret 19.

76
00:03:22,290 --> 00:03:25,380
Det første element i denne
array er placeret ved indeks nul,

77
00:03:25,380 --> 00:03:28,880
og det sidste element i denne
array er placeret ved indeks 14.

78
00:03:28,880 --> 00:03:31,430
Og så vi vil kalde dem, start og slut.

79
00:03:31,430 --> 00:03:35,387
>> Så vi beregner midtpunktet af
tilføjer 0 plus 14 divideret med 2;

80
00:03:35,387 --> 00:03:36,720
temmelig ligetil midtpunkt.

81
00:03:36,720 --> 00:03:40,190
Og vi kan sige, at
midtpunktet er nu 7.

82
00:03:40,190 --> 00:03:43,370
Så er 15, hvad vi leder efter?

83
00:03:43,370 --> 00:03:43,940
Nej, det er ej.

84
00:03:43,940 --> 00:03:45,270
Vi leder efter 19.

85
00:03:45,270 --> 00:03:49,400
Men vi ved, at 19 er større
end hvad vi findes på midten.

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

87
00:03:52,470 --> 00:03:57,280
at være lige til højre for
midtpunktet, og gentage processen igen.

88
00:03:57,280 --> 00:04:01,690
Og når vi gør det, vi nu siger den
ny start punkt er vifte placering 8.

89
00:04:01,690 --> 00:04:07,220
Hvad vi har reelt gjort, er
ignoreret alt til venstre for 15.

90
00:04:07,220 --> 00:04:09,570
Vi har fjernet halvdelen
af problemet, og nu,

91
00:04:09,570 --> 00:04:13,510
i stedet for at skulle søge
over 15 elementer i vores array,

92
00:04:13,510 --> 00:04:15,610
vi kun nødt til at søge over 7.

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

94
00:04:17,706 --> 00:04:19,600
14 er stadig slutpunktet.

95
00:04:19,600 --> 00:04:21,430
>> Og nu, vi gå over det igen.

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

97
00:04:22,810 --> 00:04:27,130
8 plus 14 er 22 divideret med 2 er 11.

98
00:04:27,130 --> 00:04:28,660
Er det, hvad vi leder efter?

99
00:04:28,660 --> 00:04:30,110
Nej, det er ej.

100
00:04:30,110 --> 00:04:32,930
Vi leder efter en værdi, der er
mindre end hvad vi lige har fundet.

101
00:04:32,930 --> 00:04:34,721
Så vi kommer til at gentage
processen igen.

102
00:04:34,721 --> 00:04:38,280
Vi kommer til at ændre slutpunktet til
være lige til venstre for midten.

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

104
00:04:41,800 --> 00:04:44,780
Og nu, det er den eneste del af
array vi nødt til at gå igennem.

105
00:04:44,780 --> 00:04:48,460
Så har vi nu elimineret
12 af de 15 elementer.

106
00:04:48,460 --> 00:04:51,550
Vi ved, at hvis 19
findes i arrayet, det

107
00:04:51,550 --> 00:04:57,210
skal eksistere et sted mellem element
nummer 8 og element nummer 10.

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

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

110
00:05:02,900 --> 00:05:05,074
Og i dette tilfælde, ser det
Målet er på midten.

111
00:05:05,074 --> 00:05:06,740
Vi fandt præcis, hvad vi leder efter.

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

113
00:05:07,780 --> 00:05:10,561
Vi fuldført
en binær søgning.

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

115
00:05:11,060 --> 00:05:13,930
Så vi ved denne algoritme
virker, hvis målet er

116
00:05:13,930 --> 00:05:16,070
et sted inde i grupperingen.

117
00:05:16,070 --> 00:05:19,060
Er denne algoritme arbejde, hvis
målet er ikke i array?

118
00:05:19,060 --> 00:05:20,810
Nå, lad os starte det
igen, og denne gang,

119
00:05:20,810 --> 00:05:23,380
lad os se efter elementet
16, som visuelt kan vi se

120
00:05:23,380 --> 00:05:25,620
findes ikke overalt i arrayet.

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

122
00:05:27,110 --> 00:05:28,590
Slutpunktet er igen 14.

123
00:05:28,590 --> 00:05:32,490
Det er de indekser i den første og
sidste elementer i komplet vifte.

124
00:05:32,490 --> 00:05:36,057
Og vi vil gå igennem den proces, vi bare
gik igennem igen, forsøger at finde 16,

125
00:05:36,057 --> 00:05:39,140
selvom visuelt, kan vi allerede
fortælle, at det ikke kommer til at være der.

126
00:05:39,140 --> 00:05:43,450
Vi ønsker blot at sikre, at denne algoritme
vil i virkeligheden stadig arbejde på en eller anden måde

127
00:05:43,450 --> 00:05:46,310
og ikke bare lade os
fast i en uendelig løkke.

128
00:05:46,310 --> 00:05:48,190
>> Så hvad er skridt først?

129
00:05:48,190 --> 00:05:50,230
Beregn midtpunktet
af den nuværende array.

130
00:05:50,230 --> 00:05:52,790
Hvad er midtpunktet
af den nuværende array?

131
00:05:52,790 --> 00:05:54,410
Tja, det er 7, ikke?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 divideret med 2 er 7.

133
00:05:57,560 --> 00:05:59,280
Er 15, hvad vi leder efter?

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

135
00:05:59,780 --> 00:06:02,930
Det er temmelig tæt, men vi leder efter
til en værdi lidt større end det.

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

137
00:06:06,310 --> 00:06:08,540
Målet er større end
hvad der er i midtpunktet.

138
00:06:08,540 --> 00:06:12,450
Og så satte vi den nye start punkt til
være lige til højre for midten.

139
00:06:12,450 --> 00:06:16,130
Midtpunktet er i øjeblikket 7, så
lad os sige den nye start punkt er 8.

140
00:06:16,130 --> 00:06:18,130
Og hvad vi har reelt
gjort igen ignoreres

141
00:06:18,130 --> 00:06:21,150
hele venstre halvdel af arrayet.

142
00:06:21,150 --> 00:06:23,750
>> Nu gentager vi den
behandle endnu en gang.

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

144
00:06:24,910 --> 00:06:29,350
8 plus 14 er 22 divideret med 2 er 11.

145
00:06:29,350 --> 00:06:31,060
Er 23, hvad vi leder efter?

146
00:06:31,060 --> 00:06:31,870
Desværre ikke.

147
00:06:31,870 --> 00:06:34,930
Vi leder efter en værdi
der er mindre end 23.

148
00:06:34,930 --> 00:06:37,850
Og så i dette tilfælde, vil vi
at ændre slutpunktet at være lige

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

150
00:06:40,035 --> 00:06:43,440
Den nuværende midtpunktet er 11, og
så vi vil sætte den nye slutpunkt

151
00:06:43,440 --> 00:06:46,980
til næste gang vi gå
gennem denne proces til 10.

152
00:06:46,980 --> 00:06:48,660
>> Igen, vi gå gennem processen igen.

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

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

155
00:06:53,100 --> 00:06:54,750
Er 19, hvad vi leder efter?

156
00:06:54,750 --> 00:06:55,500
Desværre ikke.

157
00:06:55,500 --> 00:06:58,050
Vi er stadig på udkig efter
et tal mindre end det.

158
00:06:58,050 --> 00:07:02,060
Så vi vil ændre slutpunktet denne gang
at være lige til venstre for midten.

159
00:07:02,060 --> 00:07:05,532
Midtpunktet er i øjeblikket 9,
så slutpunktet bliver 8.

160
00:07:05,532 --> 00:07:07,920
Og nu er vi bare at kigge
på et enkelt element array.

161
00:07:07,920 --> 00:07:10,250
>> Hvad er midtpunktet af dette array?

162
00:07:10,250 --> 00:07:13,459
Tja, det starter ved 8, det
slutter ved 8, midtpunktet er 8.

163
00:07:13,459 --> 00:07:14,750
Er det det, vi leder efter?

164
00:07:14,750 --> 00:07:16,339
Søger vi 17?

165
00:07:16,339 --> 00:07:17,380
Nej, vi leder efter 16.

166
00:07:17,380 --> 00:07:20,160
Så hvis den findes i arrayet,
Det skal findes et andet sted

167
00:07:20,160 --> 00:07:21,935
til venstre for hvor vi i øjeblikket er.

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

169
00:07:23,060 --> 00:07:26,610
Nå, vil vi angive slutpunktet for at være lige
til venstre for den aktuelle midtpunktet.

170
00:07:26,610 --> 00:07:29,055
Så vi vil ændre slutpunktet til 7.

171
00:07:29,055 --> 00:07:32,120
Kan du se, hvad der lige
skete her, selvom?

172
00:07:32,120 --> 00:07:33,370
Kig op her nu.

173
00:07:33,370 --> 00:07:35,970
>> Start nu større end ende.

174
00:07:35,970 --> 00:07:39,620
Effektivt, de to ender
af vores matrix har krydset,

175
00:07:39,620 --> 00:07:42,252
og startpunktet er
nu efter slutpunktet.

176
00:07:42,252 --> 00:07:43,960
Nå, der ikke
nogen mening, ikke?

177
00:07:43,960 --> 00:07:47,960
Så nu, hvad vi kan sige, er vi
har en sub vifte af størrelse 0.

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

179
00:07:50,110 --> 00:07:53,940
sikre, at element 16
findes ikke i arrayet,

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

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

182
00:07:58,340 --> 00:08:01,340
Nu bemærke, at det er en anelse
anderledes end startpunktet og slutningen

183
00:08:01,340 --> 00:08:02,900
peger være det samme.

184
00:08:02,900 --> 00:08:05,030
Hvis vi havde været leder
til 17, ville det have

185
00:08:05,030 --> 00:08:08,870
været i arrayet, og startpunktet
og slutpunkt for den sidste iteration

186
00:08:08,870 --> 00:08:11,820
før disse punkter krydses,
vi ville have fundet 17 der.

187
00:08:11,820 --> 00:08:15,510
Det er kun, når de krydser, at vi kan
sikre, at elementet ikke

188
00:08:15,510 --> 00:08:17,180
findes i arrayet.

189
00:08:17,180 --> 00:08:20,260
>> Så lad os tage en masse færre
trin end lineær søgning.

190
00:08:20,260 --> 00:08:23,250
I værste fald, havde vi
at splitte en liste over n elementer

191
00:08:23,250 --> 00:08:27,770
flere gange i halvdelen at finde målet,
enten fordi måldelen

192
00:08:27,770 --> 00:08:33,110
vil være et sted i den sidste
division, eller det findes ikke på alle.

193
00:08:33,110 --> 00:08:37,830
Så i værste fald er vi nødt til
opdele de array-- kender du?

194
00:08:37,830 --> 00:08:40,510
Log af n gange; vi
nødt til at skære problemet

195
00:08:40,510 --> 00:08:42,610
i et halvt bestemt antal gange.

196
00:08:42,610 --> 00:08:45,160
Det antal gange, er log n.

197
00:08:45,160 --> 00:08:46,510
>> Hvad er den bedste tænkelige scenarie?

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

199
00:08:48,899 --> 00:08:50,190
finder vi, hvad vi leder efter.

200
00:08:50,190 --> 00:08:52,150
I alle de foregående
eksempler på binær søgning

201
00:08:52,150 --> 00:08:55,489
vi har netop gået over, hvis vi havde
været på udkig efter elementet 15,

202
00:08:55,489 --> 00:08:57,030
vi ville have fundet det samme.

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

204
00:08:58,321 --> 00:09:01,200
Det var midtpunktet af
det første forsøg på en split

205
00:09:01,200 --> 00:09:03,950
af en division i binær søgning.

206
00:09:03,950 --> 00:09:06,350
>> Og så i værste
tilfælde binær søgning kører

207
00:09:06,350 --> 00:09:11,580
i log n, som er væsentligt bedre
end lineær søgning, i værste fald.

208
00:09:11,580 --> 00:09:16,210
I bedste fald binære
søgning kører i omega på 1.

209
00:09:16,210 --> 00:09:18,990
Så binær søgning er meget
bedre end lineær søgning,

210
00:09:18,990 --> 00:09:23,270
men du er nødt til at beskæftige sig med processen med
sortering dit array først, før du kan

211
00:09:23,270 --> 00:09:26,140
udnytte kraften i binær søgning.

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