1
00:00:00,000 --> 00:00:03,346
>> [Speel van musiek]

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

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

4
00:00:06,220 --> 00:00:08,140
So binêre soek is 'n
algoritme wat ons kan gebruik

5
00:00:08,140 --> 00:00:10,530
om 'n element te vind binne 'n skikking.

6
00:00:10,530 --> 00:00:14,710
Anders lineêre soek, dit vereis 'n
spesiale voorwaarde vooraf ontmoet het,

7
00:00:14,710 --> 00:00:19,020
maar dit is soveel meer doeltreffend as
daardie toestand is, in werklikheid, ontmoet het.

8
00:00:19,020 --> 00:00:20,470
>> So, wat is die idee hier?

9
00:00:20,470 --> 00:00:21,780
dit is Verdeel en oorwin.

10
00:00:21,780 --> 00:00:25,100
Ons wil die grootte van te verminder
die soektog gebied met 'n halwe elke keer

11
00:00:25,100 --> 00:00:27,240
ten einde 'n teiken nommer te vind.

12
00:00:27,240 --> 00:00:29,520
Dit is waar dat voorwaarde
kom in die spel, al is.

13
00:00:29,520 --> 00:00:32,740
Ons kan net die krag van die hefboom
uitskakeling helfte van die elemente

14
00:00:32,740 --> 00:00:36,070
sonder om eers na
hulle as die skikking gesorteer.

15
00:00:36,070 --> 00:00:39,200
>> As dit is 'n volledige meng,
Ons kan nie net uit die hand

16
00:00:39,200 --> 00:00:42,870
weggooi helfte van die elemente, want
ons weet nie wat ons wegdoen.

17
00:00:42,870 --> 00:00:45,624
Maar as die skikking gesorteer,
kan ons dit doen, omdat ons

18
00:00:45,624 --> 00:00:48,040
weet dat alles aan die
links van waar ons tans is

19
00:00:48,040 --> 00:00:50,500
moet laer as die wees
waarde wat ons is tans op.

20
00:00:50,500 --> 00:00:52,300
En alles aan die
reg van die plek waar ons is

21
00:00:52,300 --> 00:00:55,040
moet groter as die waarde
ons is tans op soek na.

22
00:00:55,040 --> 00:00:58,710
>> So, wat is die pseudokode
stappe vir binêre soek?

23
00:00:58,710 --> 00:01:02,310
Ons herhaal die proses totdat die
array of, as ons voortgaan deur,

24
00:01:02,310 --> 00:01:07,740
sub skikkings, kleiner stukke
die oorspronklike skikking, is die grootte 0.

25
00:01:07,740 --> 00:01:10,960
Bereken die middelpunt
van die huidige sub skikking.

26
00:01:10,960 --> 00:01:14,460
>> Indien die waarde wat jy soek is
in daardie element van die skikking, stop.

27
00:01:14,460 --> 00:01:15,030
Jy het dit gevind.

28
00:01:15,030 --> 00:01:16,550
Dit is 'n groot.

29
00:01:16,550 --> 00:01:19,610
Andersins, as die teiken is
minder as wat is aan die middel,

30
00:01:19,610 --> 00:01:23,430
so as die waarde wat ons soek
vir laer is as wat ons sien,

31
00:01:23,430 --> 00:01:26,780
herhaal hierdie proses nie, maar
verander die eindpunt, in plaas

32
00:01:26,780 --> 00:01:29,300
om die oorspronklike
voltooi volle reeks,

33
00:01:29,300 --> 00:01:34,110
wees net aan die linkerkant
van waar ons net gekyk.

34
00:01:34,110 --> 00:01:38,940
>> Ons het geweet dat die middel te hoog was,
of die teiken was minder as die middel,

35
00:01:38,940 --> 00:01:42,210
en so moet dit bestaan ​​nie, as dit
bestaan ​​op alle in die skikking,

36
00:01:42,210 --> 00:01:44,660
iewers aan die linkerkant van die middelpunt.

37
00:01:44,660 --> 00:01:48,120
En so sal ons die skikking stel
plek net aan die linkerkant

38
00:01:48,120 --> 00:01:51,145
van die middelpunt as die nuwe eindpunt.

39
00:01:51,145 --> 00:01:53,770
Omgekeerd, indien die teiken is
groter as wat is aan die middel,

40
00:01:53,770 --> 00:01:55,750
ons presies dieselfde te doen
proses, maar in plaas daarvan

41
00:01:55,750 --> 00:01:59,520
verander die begin punt om te wees
net aan die regterkant van die middelpunt

42
00:01:59,520 --> 00:02:00,680
ons het net bereken.

43
00:02:00,680 --> 00:02:03,220
En dan, weer begin ons die proses.

44
00:02:03,220 --> 00:02:05,220
>> Kom ons visualiseer dit OK?

45
00:02:05,220 --> 00:02:08,620
So is daar 'n baie gaan en hier,
maar hier is 'n verskeidenheid van die 15 elemente.

46
00:02:08,620 --> 00:02:11,400
En ons gaan word die dop
van 'n baie meer dinge hierdie tyd.

47
00:02:11,400 --> 00:02:13,870
So in lineêre soek, was ons
net omgee oor 'n teiken.

48
00:02:13,870 --> 00:02:15,869
Maar hierdie keer wil ons
omgee waar is ons

49
00:02:15,869 --> 00:02:18,480
begin om te kyk waar
ons stop soek,

50
00:02:18,480 --> 00:02:21,876
en wat is die middelpunt
van die huidige skikking.

51
00:02:21,876 --> 00:02:23,250
So hier gaan ons met binêre soek.

52
00:02:23,250 --> 00:02:25,290
Ons is pretty much goed om te gaan, reg?

53
00:02:25,290 --> 00:02:28,650
Ek gaan net om neer te sit
hieronder hier 'n stel van indekse.

54
00:02:28,650 --> 00:02:32,430
Dit is basies net wat element
van die skikking wat ons praat.

55
00:02:32,430 --> 00:02:34,500
Met lineêre soek, ons
omgee, omdat ons

56
00:02:34,500 --> 00:02:36,800
nodig om te weet hoeveel
elemente ons iterating oor,

57
00:02:36,800 --> 00:02:40,010
maar ons weet nie eintlik omgee wat
element ons is tans op soek na.

58
00:02:40,010 --> 00:02:41,014
In binêre soek, ons doen.

59
00:02:41,014 --> 00:02:42,930
En so dit is net
daar as 'n bietjie gids.

60
00:02:42,930 --> 00:02:44,910
>> So kan ons begin, reg?

61
00:02:44,910 --> 00:02:46,240
Wel, nie heeltemal nie.

62
00:02:46,240 --> 00:02:48,160
Onthou wat ek gesê het
oor binêre soek?

63
00:02:48,160 --> 00:02:50,955
Ons kan dit nie doen nie op 'n
ongesorteerde array of anders,

64
00:02:50,955 --> 00:02:55,820
ons is nie waarborg dat die
sekere elemente of waardes is nie

65
00:02:55,820 --> 00:02:57,650
per ongeluk
weggegooi toe ons net

66
00:02:57,650 --> 00:02:59,920
besluit om die helfte van die skikking te ignoreer.

67
00:02:59,920 --> 00:03:02,574
>> So stap een met binêre soek
is moet jy 'n verskeidenheid gesorteer het.

68
00:03:02,574 --> 00:03:05,240
En jy kan enige van die sortering gebruik
algoritmes ons het gepraat oor

69
00:03:05,240 --> 00:03:06,700
om jou te kry om daardie posisie.

70
00:03:06,700 --> 00:03:10,370
So nou, ons is in 'n posisie waar
kan ons binêre soek uit te voer.

71
00:03:10,370 --> 00:03:12,560
>> So laat herhaal die proses
stap vir stap en hou

72
00:03:12,560 --> 00:03:14,830
spoor van wat gebeur as ons gaan.

73
00:03:14,830 --> 00:03:17,980
So die eerste moet ons doen, is bereken
die middelpunt van die huidige skikking.

74
00:03:17,980 --> 00:03:20,620
Wel, sal ons sê ons is, in die eerste
al, op soek na die waarde 19.

75
00:03:20,620 --> 00:03:22,290
Ons probeer om die nommer 19 vind.

76
00:03:22,290 --> 00:03:25,380
Die eerste element van hierdie
verskeidenheid is geleë op indeks nul,

77
00:03:25,380 --> 00:03:28,880
en die laaste element van hierdie
verskeidenheid is geleë op 14-indeks.

78
00:03:28,880 --> 00:03:31,430
En so sal ons daardie begin en einde te bel.

79
00:03:31,430 --> 00:03:35,387
>> Sodat ons bereken die middelpunt deur
toevoeging van 0 plus 14 gedeel deur 2;

80
00:03:35,387 --> 00:03:36,720
redelik eenvoudig middelpunt.

81
00:03:36,720 --> 00:03:40,190
En ons kan sê dat
die middelpunt is nou 7.

82
00:03:40,190 --> 00:03:43,370
So is 15 wat ons soek?

83
00:03:43,370 --> 00:03:43,940
Nee dit is nie.

84
00:03:43,940 --> 00:03:45,270
Ons is op soek na 19.

85
00:03:45,270 --> 00:03:49,400
Maar ons weet dat 19 groter is
as wat ons gevind op die middel.

86
00:03:49,400 --> 00:03:52,470
>> So, wat ons kan doen is
verander die begin punt

87
00:03:52,470 --> 00:03:57,280
wees net aan die regterkant van die
middelpunt, en weer herhaal die proses.

88
00:03:57,280 --> 00:04:01,690
En wanneer ons dit doen, nou sê ons die
nuwe begin punt is verskeidenheid ligging 8.

89
00:04:01,690 --> 00:04:07,220
Wat ons gedoen het, is effektief
geïgnoreer alles aan die linkerkant van 15.

90
00:04:07,220 --> 00:04:09,570
Ons het uitgeskakel helfte
van die probleem, en nou,

91
00:04:09,570 --> 00:04:13,510
in plaas van om te soek
meer as 15 elemente in ons verskeidenheid,

92
00:04:13,510 --> 00:04:15,610
ons het net om te soek oor 7.

93
00:04:15,610 --> 00:04:17,706
So 8 is die nuwe begin punt.

94
00:04:17,706 --> 00:04:19,600
14 is nog steeds die eindpunt.

95
00:04:19,600 --> 00:04:21,430
>> En nou, ons gaan oor dit weer.

96
00:04:21,430 --> 00:04:22,810
Ons bereken die nuwe middelpunt.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 is 22, gedeel deur 2 is 11.

98
00:04:27,130 --> 00:04:28,660
Is dit wat ons soek?

99
00:04:28,660 --> 00:04:30,110
Nee dit is nie.

100
00:04:30,110 --> 00:04:32,930
Ons is op soek na 'n waarde wat
minder as wat ons nou net gevind.

101
00:04:32,930 --> 00:04:34,721
So ons gaan herhaal
die proses weer.

102
00:04:34,721 --> 00:04:38,280
Ons gaan na die eindpunt te verander
net aan die linkerkant van die middelpunt.

103
00:04:38,280 --> 00:04:41,800
So het die nuwe eindpunt word 10.

104
00:04:41,800 --> 00:04:44,780
En nou, dit is die enigste deel van
die skikking het ons om te sorteer.

105
00:04:44,780 --> 00:04:48,460
So het ons nou uitgeskakel
12 van die 15 elemente.

106
00:04:48,460 --> 00:04:51,550
Ons weet dat as 19
bestaan ​​in die skikking, dit

107
00:04:51,550 --> 00:04:57,210
moet tussen element iewers bestaan
nommer 8 en element nommer 10.

108
00:04:57,210 --> 00:04:59,400
>> So het die nuwe middelpunt weer bereken ons.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 is 18, gedeel deur 2 is 9.

110
00:05:02,900 --> 00:05:05,074
En in hierdie geval, kyk, die
teiken is op die middel.

111
00:05:05,074 --> 00:05:06,740
Ons het gevind dat presies wat ons soek.

112
00:05:06,740 --> 00:05:07,780
Ons kan stop.

113
00:05:07,780 --> 00:05:10,561
Ons suksesvol voltooi
'n binêre soek.

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

115
00:05:11,060 --> 00:05:13,930
So ons weet hierdie algoritme
werk as die teiken is

116
00:05:13,930 --> 00:05:16,070
iewers binnekant van die skikking.

117
00:05:16,070 --> 00:05:19,060
Doen hierdie algoritme werk as
die teiken is nie in die skikking?

118
00:05:19,060 --> 00:05:20,810
Wel, kom ons begin dit
weer, en hierdie keer,

119
00:05:20,810 --> 00:05:23,380
Kom ons kyk vir die element
16, wat visueel kan ons sien

120
00:05:23,380 --> 00:05:25,620
nêrens bestaan ​​in die skikking.

121
00:05:25,620 --> 00:05:27,110
>> Die begin punt is weer 0.

122
00:05:27,110 --> 00:05:28,590
Die eindpunt is weer 14.

123
00:05:28,590 --> 00:05:32,490
Dit is die indekse van die eerste en
laaste elemente van die volledige skikking.

124
00:05:32,490 --> 00:05:36,057
En ons gaan deur die proses het ons net
weer het deur, probeer om uit te vind 16,

125
00:05:36,057 --> 00:05:39,140
selfs al visueel, kan ons reeds
sê dat dit nie gaan om daar te wees.

126
00:05:39,140 --> 00:05:43,450
Ons wil net om seker te maak hierdie algoritme maak
sal, in werklikheid, nog steeds werk in een of ander manier

127
00:05:43,450 --> 00:05:46,310
en nie net laat ons
vas in 'n oneindige lus.

128
00:05:46,310 --> 00:05:48,190
>> So, wat is die stap eerste?

129
00:05:48,190 --> 00:05:50,230
Bereken die middelpunt
van die huidige skikking.

130
00:05:50,230 --> 00:05:52,790
Wat is die middelpunt
van die huidige reeks?

131
00:05:52,790 --> 00:05:54,410
Wel, dit is 7, reg?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 gedeel deur 2 is 7.

133
00:05:57,560 --> 00:05:59,280
15 wat ons soek?

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

135
00:05:59,780 --> 00:06:02,930
Dit is redelik naby, maar ons is op soek
vir 'n waarde effens groter as dit.

136
00:06:02,930 --> 00:06:06,310
>> So weet ons dat dit gaan
nêrens aan die linkerkant van 15.

137
00:06:06,310 --> 00:06:08,540
Die teiken is groter as
Wat is in die middelpunt.

138
00:06:08,540 --> 00:06:12,450
En so het ons het die nuwe begin punt om
net aan die regterkant van die middel.

139
00:06:12,450 --> 00:06:16,130
Die middelpunt is tans 7, so
Kom ons sê die nuwe begin punt is 8.

140
00:06:16,130 --> 00:06:18,130
En wat ons effektief het
weer gedoen word geïgnoreer

141
00:06:18,130 --> 00:06:21,150
die hele linker helfte van die skikking.

142
00:06:21,150 --> 00:06:23,750
>> Nou, ons herhaal die
verwerk een keer.

143
00:06:23,750 --> 00:06:24,910
Bereken die nuwe middelpunt.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 is 22, gedeel deur 2 is 11.

145
00:06:29,350 --> 00:06:31,060
Is 23 wat ons soek?

146
00:06:31,060 --> 00:06:31,870
Ongelukkig nie.

147
00:06:31,870 --> 00:06:34,930
Ons is op soek na 'n waarde
dit is minder as 23.

148
00:06:34,930 --> 00:06:37,850
En so in hierdie geval, ons gaan
tot aan die einde punt te verander na net

149
00:06:37,850 --> 00:06:40,035
aan die linkerkant van die huidige middelpunt.

150
00:06:40,035 --> 00:06:43,440
Die huidige middelpunt is 11, en
so sal ons die nuwe eindpunt stel

151
00:06:43,440 --> 00:06:46,980
vir die volgende keer gaan ons
deur hierdie proses tot 10.

152
00:06:46,980 --> 00:06:48,660
>> Weereens, ons gaan deur die proses weer.

153
00:06:48,660 --> 00:06:49,640
Bereken die middelpunt.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 gedeel deur 2 is 9.

155
00:06:53,100 --> 00:06:54,750
Is 19 wat ons soek?

156
00:06:54,750 --> 00:06:55,500
Ongelukkig nie.

157
00:06:55,500 --> 00:06:58,050
Ons is nog op soek na
'n aantal minder as dit.

158
00:06:58,050 --> 00:07:02,060
So sal ons die eindpunt hierdie tyd verander
wees net aan die linkerkant van die middelpunt.

159
00:07:02,060 --> 00:07:05,532
Die middelpunt is tans 9,
so die eindpunt sal wees 8.

160
00:07:05,532 --> 00:07:07,920
En nou, ons soek net
op 'n enkele element skikking.

161
00:07:07,920 --> 00:07:10,250
>> Wat is die middelpunt van hierdie verskeidenheid?

162
00:07:10,250 --> 00:07:13,459
Wel, dit begin by 8, is dit
eindig by 8, die middelpunt is 8.

163
00:07:13,459 --> 00:07:14,750
Is dit wat ons soek?

164
00:07:14,750 --> 00:07:16,339
Is ons op soek na 17?

165
00:07:16,339 --> 00:07:17,380
Nee, ons is op soek na 16.

166
00:07:17,380 --> 00:07:20,160
So as dit bestaan ​​in die skikking,
dit moet êrens bestaan

167
00:07:20,160 --> 00:07:21,935
aan die linkerkant van waar ons tans is.

168
00:07:21,935 --> 00:07:23,060
So, wat gaan ons doen?

169
00:07:23,060 --> 00:07:26,610
Wel, ons sal die einde punt stel om net
aan die linkerkant van die huidige middelpunt.

170
00:07:26,610 --> 00:07:29,055
So sal ons die eindpunt te verander na 7.

171
00:07:29,055 --> 00:07:32,120
Sien jy wat net
hier gebeur, al is?

172
00:07:32,120 --> 00:07:33,370
Kyk nou hier.

173
00:07:33,370 --> 00:07:35,970
>> Begin nou groter as die einde.

174
00:07:35,970 --> 00:07:39,620
Effektief, die twee ente
van ons verskeidenheid gekruis het,

175
00:07:39,620 --> 00:07:42,252
en die begin punt is
nou na die eindpunt.

176
00:07:42,252 --> 00:07:43,960
Wel, dit doen nie
maak geen sin, reg?

177
00:07:43,960 --> 00:07:47,960
So nou, wat ons kan sê, is ons
'n sub verskeidenheid van grootte 0.

178
00:07:47,960 --> 00:07:50,110
En sodra ons gekry om
hierdie punt, kan ons nou

179
00:07:50,110 --> 00:07:53,940
waarborg dat element 16
bestaan ​​nie in die skikking,

180
00:07:53,940 --> 00:07:56,280
omdat die begin punt
en eindpunt gekruis het.

181
00:07:56,280 --> 00:07:58,340
En so is dit nie daar nie.

182
00:07:58,340 --> 00:08:01,340
Nou, sien dat hierdie is 'n bietjie
anders as die begin en die einde punt

183
00:08:01,340 --> 00:08:02,900
punt is dieselfde.

184
00:08:02,900 --> 00:08:05,030
As ons was op soek
vir 17, sou dit

185
00:08:05,030 --> 00:08:08,870
in die skikking, en die begin punt is
en eindpunt van die laaste iterasie

186
00:08:08,870 --> 00:08:11,820
voordat die punte oorgesteek,
Ons sou daar gevind 17.

187
00:08:11,820 --> 00:08:15,510
Dit is net wanneer hulle oor wat ons kan
waarborg dat die element nie

188
00:08:15,510 --> 00:08:17,180
bestaan ​​in die skikking.

189
00:08:17,180 --> 00:08:20,260
>> So laat ons 'n baie minder
stappe as lineêre soek.

190
00:08:20,260 --> 00:08:23,250
In die ergste geval scenario, het ons
te verdeel 'n lys van n elemente

191
00:08:23,250 --> 00:08:27,770
herhaaldelik in die helfte om die teiken te vind,
óf omdat die teiken element

192
00:08:27,770 --> 00:08:33,110
sal in die laaste iewers
afdeling, of dit nie bestaan ​​nie by almal.

193
00:08:33,110 --> 00:08:37,830
So in die ergste geval, ons het om te
verdeel die array-- weet jy?

194
00:08:37,830 --> 00:08:40,510
Teken van n keer; ons
het om die probleem op te sny

195
00:08:40,510 --> 00:08:42,610
in die helfte van 'n sekere aantal kere.

196
00:08:42,610 --> 00:08:45,160
Dat die getal kere is log n.

197
00:08:45,160 --> 00:08:46,510
>> Wat is die beste scenario?

198
00:08:46,510 --> 00:08:48,899
Wel, die eerste keer dat ons
bereken die middelpunt,

199
00:08:48,899 --> 00:08:50,190
vind ons wat ons soek.

200
00:08:50,190 --> 00:08:52,150
In al die vorige
voorbeelde van binêre soek

201
00:08:52,150 --> 00:08:55,489
Ons het net gegaan oor, as ons het
is op soek na die element 15,

202
00:08:55,489 --> 00:08:57,030
ons dat onmiddellik sou gevind het.

203
00:08:57,030 --> 00:08:58,321
Dit was aan die begin.

204
00:08:58,321 --> 00:09:01,200
Dit was die middelpunt van
die eerste poging om 'n skeuring

205
00:09:01,200 --> 00:09:03,950
van 'n afdeling in binêre soek.

206
00:09:03,950 --> 00:09:06,350
>> En so in die ergste
geval, binêre soek loop

207
00:09:06,350 --> 00:09:11,580
in log N, wat aansienlik beter
as lineêre soek, in die ergste geval.

208
00:09:11,580 --> 00:09:16,210
In die beste geval, binêre
soek lopies in omega van 1.

209
00:09:16,210 --> 00:09:18,990
So binêre soek is 'n baie
beter as lineêre soek,

210
00:09:18,990 --> 00:09:23,270
maar jy het om te gaan met die proses van
sorteer jou array eerste voordat jy kan

211
00:09:23,270 --> 00:09:26,140
die invloed van die krag van binêre soek.

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

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

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