1
00:00:00,000 --> 00:00:03,346
>> [Muziek]

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

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

4
00:00:06,220 --> 00:00:08,140
Dus binary search is een
algoritme we kunnen gebruiken

5
00:00:08,140 --> 00:00:10,530
een element vindt in een matrix.

6
00:00:10,530 --> 00:00:14,710
Unlike lineair zoeken, vereist een
speciale voorwaarden vooraf worden voldaan,

7
00:00:14,710 --> 00:00:19,020
maar het is zo veel efficiënter als
deze voorwaarde is in feite ontmoet.

8
00:00:19,020 --> 00:00:20,470
>> Dus wat is het idee hier?

9
00:00:20,470 --> 00:00:21,780
het is verdeel en heers.

10
00:00:21,780 --> 00:00:25,100
We willen de grootte van de te verminderen
het zoekgebied met de helft elke keer

11
00:00:25,100 --> 00:00:27,240
teneinde een target nummer.

12
00:00:27,240 --> 00:00:29,520
Dit is waar dat de toestand
in het spel komt, dat wel.

13
00:00:29,520 --> 00:00:32,740
We kunnen alleen maar de kracht van het hefboomeffect
waardoor de helft van de elementen

14
00:00:32,740 --> 00:00:36,070
zonder zelfs maar te kijken naar
ze als de array wordt gesorteerd.

15
00:00:36,070 --> 00:00:39,200
>> Als het een complete mix,
We kunnen niet zomaar uit de hand

16
00:00:39,200 --> 00:00:42,870
gooi de helft van de elementen, omdat
we weten niet wat we weggooien.

17
00:00:42,870 --> 00:00:45,624
Maar als de matrix wordt gesorteerd,
kunnen we dat doen, omdat we

18
00:00:45,624 --> 00:00:48,040
weet dat alles aan de
links van waar we nu zijn

19
00:00:48,040 --> 00:00:50,500
moet lager zijn dan de
waar we momenteel.

20
00:00:50,500 --> 00:00:52,300
En alles aan de
rechts van waar we zijn

21
00:00:52,300 --> 00:00:55,040
groter zijn dan de waarde
we bent momenteel.

22
00:00:55,040 --> 00:00:58,710
>> Dus wat is het pseudocode
stappen voor binaire zoeken?

23
00:00:58,710 --> 00:01:02,310
We herhalen dit proces tot de
array of, als we verder door,

24
00:01:02,310 --> 00:01:07,740
sub arrays kleinere stukken
de oorspronkelijke array, is de grootte 0.

25
00:01:07,740 --> 00:01:10,960
Bereken het middelpunt
van de huidige sub-array.

26
00:01:10,960 --> 00:01:14,460
>> Als de waarde die u zoekt naar
in dat element van de array stoppen.

27
00:01:14,460 --> 00:01:15,030
U vond het.

28
00:01:15,030 --> 00:01:16,550
Dat is geweldig.

29
00:01:16,550 --> 00:01:19,610
Anders, als het doel
minder dan wat er in het midden,

30
00:01:19,610 --> 00:01:23,430
dus als de waarde die we zoeken
voor het lager is dan wat we zien,

31
00:01:23,430 --> 00:01:26,780
herhaal dit proces, maar
wijzigt het eindpunt, in plaats

32
00:01:26,780 --> 00:01:29,300
dat het de originele
voltooien volledige reeks,

33
00:01:29,300 --> 00:01:34,110
zijn net aan de linkerkant
waar we keek.

34
00:01:34,110 --> 00:01:38,940
>> We wisten dat het midden te hoog was,
of het doelwit was lager dan het midden,

35
00:01:38,940 --> 00:01:42,210
en dus moet bestaan, indien
al bestaat in de array,

36
00:01:42,210 --> 00:01:44,660
iets links van het midden.

37
00:01:44,660 --> 00:01:48,120
En dus zullen we de array ingesteld
locatie net aan de linkerkant

38
00:01:48,120 --> 00:01:51,145
van het middelpunt als het nieuwe eindpunt.

39
00:01:51,145 --> 00:01:53,770
Omgekeerd, als het doel
groter dan wat er in het midden,

40
00:01:53,770 --> 00:01:55,750
we precies hetzelfde doen
proces, maar we

41
00:01:55,750 --> 00:01:59,520
wijzigt het beginpunt te zijn
net rechts van het middelpunt

42
00:01:59,520 --> 00:02:00,680
we net berekend.

43
00:02:00,680 --> 00:02:03,220
En dan opnieuw beginnen we het proces.

44
00:02:03,220 --> 00:02:05,220
>> Laten we dit visualiseren, OK?

45
00:02:05,220 --> 00:02:08,620
Dus er is veel te doen en hier,
maar hier is een array van 15 elementen.

46
00:02:08,620 --> 00:02:11,400
En we gaan worden bijhouden
van veel meer dingen deze keer.

47
00:02:11,400 --> 00:02:13,870
Dus in lineair zoeken, waren we
gewoon zorgen te maken over een doel.

48
00:02:13,870 --> 00:02:15,869
Maar deze keer willen we
schelen waar zijn we

49
00:02:15,869 --> 00:02:18,480
beginnen te kijken, waar de
stoppen we kijken,

50
00:02:18,480 --> 00:02:21,876
en wat is het middelpunt
van de huidige rij.

51
00:02:21,876 --> 00:02:23,250
Dus hier gaan we met binaire zoeken.

52
00:02:23,250 --> 00:02:25,290
We zijn vrij veel goed om te gaan, toch?

53
00:02:25,290 --> 00:02:28,650
Ik ga gewoon neer te zetten
Hieronder hier een set indices.

54
00:02:28,650 --> 00:02:32,430
Dit is eigenlijk precies wat element
van de array we het over hebben.

55
00:02:32,430 --> 00:02:34,500
Met lineair zoeken wij
zorg, aangezien we

56
00:02:34,500 --> 00:02:36,800
moeten weten hoeveel
elementen we itereren over,

57
00:02:36,800 --> 00:02:40,010
maar we eigenlijk niet schelen wat
element we bent momenteel.

58
00:02:40,010 --> 00:02:41,014
In binaire zoeken, we doen.

59
00:02:41,014 --> 00:02:42,930
En dus die zijn
daar als een kleine gids.

60
00:02:42,930 --> 00:02:44,910
>> Dus we kunnen beginnen, toch?

61
00:02:44,910 --> 00:02:46,240
Nou, niet helemaal.

62
00:02:46,240 --> 00:02:48,160
Vergeet niet wat ik zei
ongeveer binaire zoeken?

63
00:02:48,160 --> 00:02:50,955
We kunnen het niet op
ongesorteerde array of anders,

64
00:02:50,955 --> 00:02:55,820
wij niet garanderen dat de
bepaalde elementen of waarden niet

65
00:02:55,820 --> 00:02:57,650
ongeluk
weggegooid toen we net

66
00:02:57,650 --> 00:02:59,920
besluiten helft van de matrix negeren.

67
00:02:59,920 --> 00:03:02,574
>> Dus stap één met binaire zoeken
is dat je moet een gesorteerde array.

68
00:03:02,574 --> 00:03:05,240
En je kunt een van de sortering gebruiken
algoritmes we hebben gesproken over

69
00:03:05,240 --> 00:03:06,700
om u naar die positie.

70
00:03:06,700 --> 00:03:10,370
Dus nu zijn we in een positie waar
kunnen we binaire zoeken.

71
00:03:10,370 --> 00:03:12,560
>> Dus laten we het proces herhalen
stap voor stap en houden

72
00:03:12,560 --> 00:03:14,830
spoor van wat er gebeurt als we verder gaan.

73
00:03:14,830 --> 00:03:17,980
Dus de eerste moeten we doen is te berekenen
het middelpunt van de huidige rij.

74
00:03:17,980 --> 00:03:20,620
Nou, zullen we zeggen dat we in de eerste plaats
alle, op zoek naar de waarde 19.

75
00:03:20,620 --> 00:03:22,290
We proberen om het nummer 19 te vinden.

76
00:03:22,290 --> 00:03:25,380
Het eerste element van deze
matrix zich op index nul,

77
00:03:25,380 --> 00:03:28,880
en het laatste element van deze
matrix zich op index 14.

78
00:03:28,880 --> 00:03:31,430
En dus zullen we die begin en einde noemen.

79
00:03:31,430 --> 00:03:35,387
>> Dus we berekenen het middelpunt van
het toevoegen van 0 plus 14 gedeeld door 2;

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

81
00:03:36,720 --> 00:03:40,190
En we kunnen zeggen dat
het middelpunt is nu 7.

82
00:03:40,190 --> 00:03:43,370
Zo is 15 wat we zoeken?

83
00:03:43,370 --> 00:03:43,940
Nee, dat is het niet.

84
00:03:43,940 --> 00:03:45,270
We zijn op zoek naar 19.

85
00:03:45,270 --> 00:03:49,400
Maar we weten dat 19 groter
dan wat we in het midden.

86
00:03:49,400 --> 00:03:52,470
>> Dus wat we kunnen doen is
wijzigt het beginpunt

87
00:03:52,470 --> 00:03:57,280
om net rechts van het
middelpunt, en herhaal het proces.

88
00:03:57,280 --> 00:04:01,690
En als we dat doen, nu zeggen we het
nieuwe start punt is scala locatie 8.

89
00:04:01,690 --> 00:04:07,220
Wat we hebben gedaan is effectief
genegeerd alle links van 15.

90
00:04:07,220 --> 00:04:09,570
We hebben geëlimineerd de helft
van het probleem, en nu,

91
00:04:09,570 --> 00:04:13,510
in plaats van te zoeken
meer dan 15 elementen in onze array,

92
00:04:13,510 --> 00:04:15,610
we hebben alleen te zoeken meer dan 7.

93
00:04:15,610 --> 00:04:17,706
Dus 8 is het nieuwe startpunt.

94
00:04:17,706 --> 00:04:19,600
14 blijft het eindpunt.

95
00:04:19,600 --> 00:04:21,430
>> En nu gaan we dan dit weer.

96
00:04:21,430 --> 00:04:22,810
We berekenen de nieuwe middelpunt.

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

98
00:04:27,130 --> 00:04:28,660
Is dit wat we zoeken?

99
00:04:28,660 --> 00:04:30,110
Nee, dat is het niet.

100
00:04:30,110 --> 00:04:32,930
We zijn op zoek naar een waarde die is
minder dan wat we vonden.

101
00:04:32,930 --> 00:04:34,721
Dus we gaan om te herhalen
het proces opnieuw.

102
00:04:34,721 --> 00:04:38,280
We gaan naar het eindpunt te veranderen
net links van het midden.

103
00:04:38,280 --> 00:04:41,800
Zodat het nieuwe eindpunt wordt 10.

104
00:04:41,800 --> 00:04:44,780
En nu, dat is het enige deel van
de serie hebben we te sorteren.

105
00:04:44,780 --> 00:04:48,460
Dus hebben we nu geëlimineerd
12 van de 15 elementen.

106
00:04:48,460 --> 00:04:51,550
We weten dat als 19
bestaat in de array, zij

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

108
00:04:57,210 --> 00:04:59,400
>> Dus de nieuwe middelpunt opnieuw berekenen we.

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

110
00:05:02,900 --> 00:05:05,074
En in dit geval, kijk, de
doelstelling is in het midden.

111
00:05:05,074 --> 00:05:06,740
Vonden we precies wat we zoeken.

112
00:05:06,740 --> 00:05:07,780
We kunnen stoppen.

113
00:05:07,780 --> 00:05:10,561
We succesvol afgerond
een binair zoeken.

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

115
00:05:11,060 --> 00:05:13,930
Dus we weten dit algoritme
werkt als het doel is

116
00:05:13,930 --> 00:05:16,070
ergens in de array.

117
00:05:16,070 --> 00:05:19,060
Doet dit algoritme werk als
het doel niet in de array?

118
00:05:19,060 --> 00:05:20,810
Nou, laten we starten
weer en ditmaal,

119
00:05:20,810 --> 00:05:23,380
laten we eens kijken naar het element
16, die visueel kunnen we zien

120
00:05:23,380 --> 00:05:25,620
bestaat nergens in de array.

121
00:05:25,620 --> 00:05:27,110
>> Het startpunt is weer 0.

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

123
00:05:28,590 --> 00:05:32,490
Dat zijn de indices van de eerste en
laatste elementen van de volledige array.

124
00:05:32,490 --> 00:05:36,057
En we gaan door middel van het proces dat we net
weer ging door, proberen te vinden 16,

125
00:05:36,057 --> 00:05:39,140
hoewel visueel, kunnen we nu al
vertellen dat het niet gaat om daar te zijn.

126
00:05:39,140 --> 00:05:43,450
We willen gewoon zeker van dat dit algoritme
zal in feite nog steeds werken op een bepaalde manier

127
00:05:43,450 --> 00:05:46,310
en niet alleen laat ons
geplakt in een oneindige lus.

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

129
00:05:48,190 --> 00:05:50,230
Bereken het middelpunt
van de huidige rij.

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

131
00:05:52,790 --> 00:05:54,410
Nou, het is 7, toch?

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

133
00:05:57,560 --> 00:05:59,280
Is 15 wat we zoeken?

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

135
00:05:59,780 --> 00:06:02,930
Het is vrij dicht, maar we zijn op zoek
voor een waarde iets groter dan dat.

136
00:06:02,930 --> 00:06:06,310
>> Dus we weten dat het gaat om
zijn nergens links van 15.

137
00:06:06,310 --> 00:06:08,540
Het doel is groter dan
wat er in het midden.

138
00:06:08,540 --> 00:06:12,450
En dus zetten we de nieuwe start punt
net rechts van het midden.

139
00:06:12,450 --> 00:06:16,130
Het middelpunt is momenteel 7, zodat
laten we zeggen dat het nieuwe startpunt is 8.

140
00:06:16,130 --> 00:06:18,130
En wat we effectief hebt
weer gedaan wordt genegeerd

141
00:06:18,130 --> 00:06:21,150
het gehele linkerhelft van de array.

142
00:06:21,150 --> 00:06:23,750
>> Nu, we herhalen
verwerken nog een keer.

143
00:06:23,750 --> 00:06:24,910
Bereken het nieuwe middelpunt.

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

145
00:06:29,350 --> 00:06:31,060
23 is wat we zoeken?

146
00:06:31,060 --> 00:06:31,870
Helaas niet.

147
00:06:31,870 --> 00:06:34,930
We zijn op zoek naar een waarde
die kleiner is dan 23.

148
00:06:34,930 --> 00:06:37,850
En dus in dit geval, we gaan
het eindpunt veranderen gewoon

149
00:06:37,850 --> 00:06:40,035
links van het huidige middelpunt.

150
00:06:40,035 --> 00:06:43,440
De huidige middelpunt is 11, en
dus zullen we de nieuwe eindpunt in te stellen

151
00:06:43,440 --> 00:06:46,980
voor de volgende keer dat we gaan
door dit proces te 10.

152
00:06:46,980 --> 00:06:48,660
>> Nogmaals, we gaan door het proces opnieuw.

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

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

155
00:06:53,100 --> 00:06:54,750
19 is wat we zoeken?

156
00:06:54,750 --> 00:06:55,500
Helaas niet.

157
00:06:55,500 --> 00:06:58,050
We zijn nog op zoek naar
een getal kleiner dan dat.

158
00:06:58,050 --> 00:07:02,060
Dus we het eindpunt van deze tijd te veranderen
zijn net links van het midden.

159
00:07:02,060 --> 00:07:05,532
Het middelpunt is momenteel 9,
dus het eindpunt zal zijn 8.

160
00:07:05,532 --> 00:07:07,920
En nu, we zijn gewoon op zoek
in een enkel element array.

161
00:07:07,920 --> 00:07:10,250
>> Wat is het middelpunt van deze serie?

162
00:07:10,250 --> 00:07:13,459
Nou, het begint op 8, dat
8 eindigt bij het middelpunt is 8.

163
00:07:13,459 --> 00:07:14,750
Is dat wat we zoeken?

164
00:07:14,750 --> 00:07:16,339
Zijn wij op zoek naar 17?

165
00:07:16,339 --> 00:07:17,380
Nee, we zijn op zoek naar 16.

166
00:07:17,380 --> 00:07:20,160
Dus indien aanwezig in de matrix,
moet ergens aanwezig

167
00:07:20,160 --> 00:07:21,935
aan de linkerkant van waar we nu zijn.

168
00:07:21,935 --> 00:07:23,060
Dus wat gaan we doen?

169
00:07:23,060 --> 00:07:26,610
Nou, we zullen het eindpunt in te stellen om alleen te zijn
links van het huidige middelpunt.

170
00:07:26,610 --> 00:07:29,055
Dus we het eindpunt te veranderen tot 7.

171
00:07:29,055 --> 00:07:32,120
Zie je wat er zojuist
is hier gebeurd, hoewel?

172
00:07:32,120 --> 00:07:33,370
Kijk hier nu.

173
00:07:33,370 --> 00:07:35,970
>> Start is nu groter dan eind.

174
00:07:35,970 --> 00:07:39,620
Effectief, de beide einden
van ons aanbod hebben gekruist,

175
00:07:39,620 --> 00:07:42,252
en het startpunt is
nu na het eindpunt.

176
00:07:42,252 --> 00:07:43,960
Nou, dat doet niet
geen zin, toch?

177
00:07:43,960 --> 00:07:47,960
Dus nu, wat we kunnen zeggen is dat we
een sub-matrix van grootte 0.

178
00:07:47,960 --> 00:07:50,110
En zodra we gekregen om
dit punt, kunnen we nu

179
00:07:50,110 --> 00:07:53,940
waarborgen dat element 16
bestaat niet in de array,

180
00:07:53,940 --> 00:07:56,280
omdat het beginpunt
en eindpunt hebben gekruist.

181
00:07:56,280 --> 00:07:58,340
En dus is het er niet.

182
00:07:58,340 --> 00:08:01,340
Nu, merken dat dit is iets
anders dan het begin en eindpunt

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

184
00:08:02,900 --> 00:08:05,030
Als we waren op zoek
17, zou het

185
00:08:05,030 --> 00:08:08,870
in de array, en het startpunt geweest
en eindpunt van die laatste iteratie

186
00:08:08,870 --> 00:08:11,820
voor die punten gekruist,
we zouden er hebben 17.

187
00:08:11,820 --> 00:08:15,510
Het is pas wanneer ze steken dat we kunnen
waarborgen dat het element niet

188
00:08:15,510 --> 00:08:17,180
bestaan ​​in de array.

189
00:08:17,180 --> 00:08:20,260
>> Dus laten we eens een stuk minder
stappen dan lineair zoeken.

190
00:08:20,260 --> 00:08:23,250
In het ergste geval, hadden we
op te splitsen een lijst van n elementen

191
00:08:23,250 --> 00:08:27,770
herhaaldelijk helft het doel te vinden,
hetzij omdat het doelelement

192
00:08:27,770 --> 00:08:33,110
zal in de laatste ergens
divisie of het niet bestaat helemaal niet.

193
00:08:33,110 --> 00:08:37,830
Dus in het ergste geval, we
splitsen de array-- weet je dat?

194
00:08:37,830 --> 00:08:40,510
Log n keer; we
het probleem moeten snijden

195
00:08:40,510 --> 00:08:42,610
in halve bepaald aantal keren.

196
00:08:42,610 --> 00:08:45,160
Dat aantal keren is log n.

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

198
00:08:46,510 --> 00:08:48,899
Nou, de eerste keer dat we
berekent het middelpunt,

199
00:08:48,899 --> 00:08:50,190
we vinden wat we zoeken.

200
00:08:50,190 --> 00:08:52,150
In alle voorgaande
voorbeelden op binaire zoekopdracht

201
00:08:52,150 --> 00:08:55,489
we hebben gewoon weg over, als we hadden
op zoek naar het element 15,

202
00:08:55,489 --> 00:08:57,030
we die onmiddellijk zou hebben gevonden.

203
00:08:57,030 --> 00:08:58,321
Dat was in het begin.

204
00:08:58,321 --> 00:09:01,200
Dat was het middelpunt van
de eerste poging tot een split

205
00:09:01,200 --> 00:09:03,950
van een divisie in binaire zoeken.

206
00:09:03,950 --> 00:09:06,350
>> En zo in het ergste
geval, binary search loopt

207
00:09:06,350 --> 00:09:11,580
log n, die aanzienlijk beter
dan lineair zoeken, in het ergste geval.

208
00:09:11,580 --> 00:09:16,210
In het beste geval binary
search draait in omega van 1.

209
00:09:16,210 --> 00:09:18,990
Dus binaire zoektocht is een veel
beter dan lineaire zoeken,

210
00:09:18,990 --> 00:09:23,270
maar heb je te maken met het proces van de
sorteren van de array eerst voordat je kunt

211
00:09:23,270 --> 00:09:26,140
maken gebruik van de kracht van de binaire zoekopdracht.

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

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

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