1
00:00:00,000 --> 00:00:03,346
>> [Zenelejátszási]

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

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

4
00:00:06,220 --> 00:00:08,140
Tehát bináris keresés egy
algoritmust tudjuk használni

5
00:00:08,140 --> 00:00:10,530
találni egy elem belsejében egy tömbben.

6
00:00:10,530 --> 00:00:14,710
Ellentétben a lineáris keresési van szükség, mert
különleges feltételt kell teljesíteni előre,

7
00:00:14,710 --> 00:00:19,020
de ez annyira sokkal hatékonyabb, ha
ez a feltétel, sőt, teljesülnek.

8
00:00:19,020 --> 00:00:20,470
>> Tehát mi az ötlet?

9
00:00:20,470 --> 00:00:21,780
ez Oszd meg és uralkodj.

10
00:00:21,780 --> 00:00:25,100
Azt akarjuk, hogy csökkentsék a méretét
A keresési terület felére minden alkalommal

11
00:00:25,100 --> 00:00:27,240
annak érdekében, hogy megtalálják a célszámot.

12
00:00:27,240 --> 00:00:29,520
Ez az, ahol ez a feltétel
jön szóba, mégis.

13
00:00:29,520 --> 00:00:32,740
Mi csak kihasználja az erejét
kiküszöbölve a fele az elemek

14
00:00:32,740 --> 00:00:36,070
Anélkül, hogy megvizsgálnák
azokat, ha a tömb rendezve.

15
00:00:36,070 --> 00:00:39,200
>> Ha ez egy komplett mix,
Nem lehet csak a kezét

16
00:00:39,200 --> 00:00:42,870
dobja a fele a elemek, mert
nem tudjuk, hogy mi vagyunk elöntve.

17
00:00:42,870 --> 00:00:45,624
De ha a tömb rendezve,
tehetünk, hogy azért, mert

18
00:00:45,624 --> 00:00:48,040
tudni, hogy minden a
balra, ahol jelenleg is

19
00:00:48,040 --> 00:00:50,500
kell lennie, alacsonyabb, mint a
értéke vagyunk jelenleg.

20
00:00:50,500 --> 00:00:52,300
És mindent az
jobbra, hol vagyunk

21
00:00:52,300 --> 00:00:55,040
nagyobbnak kell lennie, mint az az érték
mi jelenleg keresi a.

22
00:00:55,040 --> 00:00:58,710
>> Szóval mi a pszeudokódja
lépések bináris keresés?

23
00:00:58,710 --> 00:01:02,310
Mi ismételje meg ezt a folyamatot, amíg a
tömb vagy, ahogy haladunk keresztül,

24
00:01:02,310 --> 00:01:07,740
sub tömbök, kisebb darabok
Az eredeti tömb, a 0-ás méretű.

25
00:01:07,740 --> 00:01:10,960
Számolja ki a középpont
Az aktuális al tömb.

26
00:01:10,960 --> 00:01:14,460
>> Ha az érték, amit keres
abban a tömb elemének, hagyja abba.

27
00:01:14,460 --> 00:01:15,030
Megtaláltad.

28
00:01:15,030 --> 00:01:16,550
Az remek.

29
00:01:16,550 --> 00:01:19,610
Ellenkező esetben, ha a cél az,
kevesebb, mint mi a középső,

30
00:01:19,610 --> 00:01:23,430
így ha az érték keresünk
A kisebb, mint amit látunk,

31
00:01:23,430 --> 00:01:26,780
ismételje meg ezt a folyamatot újra, de
változtatni a végpont helyett

32
00:01:26,780 --> 00:01:29,300
az, hogy az eredeti
befejezni a teljes tömb,

33
00:01:29,300 --> 00:01:34,110
hogy csak a bal
A ahol csak nézett.

34
00:01:34,110 --> 00:01:38,940
>> Tudtuk, hogy a középső túl magas volt,
vagy a cél volt, kisebb, mint a középső,

35
00:01:38,940 --> 00:01:42,210
és így is léteznie kell, ha
egyáltalán létezik a tömbben,

36
00:01:42,210 --> 00:01:44,660
valahol a bal oldalon a középpont.

37
00:01:44,660 --> 00:01:48,120
És így fogunk állítani a tömb
helyen, csak a bal

38
00:01:48,120 --> 00:01:51,145
A középpont az új végpontot.

39
00:01:51,145 --> 00:01:53,770
Ezzel szemben, ha a cél az,
nagyobb, mint mi a középső,

40
00:01:53,770 --> 00:01:55,750
mi pontosan ugyanazt
folyamat, de ehelyett

41
00:01:55,750 --> 00:01:59,520
változtatni a kezdőpontot, hogy
csak a jobb oldalon a középpont

42
00:01:59,520 --> 00:02:00,680
mi csak kiszámítani.

43
00:02:00,680 --> 00:02:03,220
És akkor kezdjük újra az eljárást.

44
00:02:03,220 --> 00:02:05,220
>> Nézzük elképzelni, rendben?

45
00:02:05,220 --> 00:02:08,620
Szóval van egy csomó folyik, és itt,
de itt van egy tömbben a 15 elemet.

46
00:02:08,620 --> 00:02:11,400
És mi lesz, hogy nyomon követhetőek
sokkal több dolgot ebben az időben.

47
00:02:11,400 --> 00:02:13,870
Tehát a lineáris keresés voltunk
Csak törődve a cél.

48
00:02:13,870 --> 00:02:15,869
De ezúttal szeretnénk
törődnek hol vagyunk

49
00:02:15,869 --> 00:02:18,480
kezdi meg, ahol
álltunk keres,

50
00:02:18,480 --> 00:02:21,876
és mi van a középpont
A jelenlegi tömb.

51
00:02:21,876 --> 00:02:23,250
Tehát itt vagyunk a bináris keresés.

52
00:02:23,250 --> 00:02:25,290
Nem vagyunk elég sok jó menni, igaz?

53
00:02:25,290 --> 00:02:28,650
Csak megyek letenni
Az alábbi Itt egy sor mutatót.

54
00:02:28,650 --> 00:02:32,430
Ez alapvetően csak mi elem
A tömb beszélünk.

55
00:02:32,430 --> 00:02:34,500
A lineáris keresés, akkor
érdekel, mivel azt

56
00:02:34,500 --> 00:02:36,800
tudnia kell, hogy hány
elemek mi az iterációt,

57
00:02:36,800 --> 00:02:40,010
de valójában nem érdekel, mit
eleme, hogy jelenleg további nézi.

58
00:02:40,010 --> 00:02:41,014
A bináris keresés, amit csinálunk.

59
00:02:41,014 --> 00:02:42,930
És így ezek csak
ott, mint egy kis útmutató.

60
00:02:42,930 --> 00:02:44,910
>> Így tudjuk kezdeni, ugye?

61
00:02:44,910 --> 00:02:46,240
Nos, nem egészen.

62
00:02:46,240 --> 00:02:48,160
Emlékszel, mit mondtam
a bináris keresés?

63
00:02:48,160 --> 00:02:50,955
Nem tehetjük meg egy
szétválogatás nélkül tömb vagy más,

64
00:02:50,955 --> 00:02:55,820
mi nem garantálja, hogy a
Bizonyos elemek vagy értékek nem

65
00:02:55,820 --> 00:02:57,650
véletlen
dobni, amikor már csak

66
00:02:57,650 --> 00:02:59,920
úgy dönt, hogy figyelmen kívül hagyja a fele a tömbben.

67
00:02:59,920 --> 00:03:02,574
>> Szóval lépés egy bináris keresés
ez kell egy rendezett tömbben.

68
00:03:02,574 --> 00:03:05,240
És akkor használja a válogatás
algoritmusok beszéltünk

69
00:03:05,240 --> 00:03:06,700
rávenni, hogy ezt az álláspontot.

70
00:03:06,700 --> 00:03:10,370
Tehát most vagyunk abban a helyzetben, ahol
tudjuk elvégezni bináris keresés.

71
00:03:10,370 --> 00:03:12,560
>> Úgyhogy ismételje meg a folyamatot
lépésről lépésre, és tartsa

72
00:03:12,560 --> 00:03:14,830
követni, hogy mi történik, ahogy haladunk.

73
00:03:14,830 --> 00:03:17,980
Tehát az első meg kell tennie, hogy számítani
a középpontját a jelenlegi tömb.

74
00:03:17,980 --> 00:03:20,620
Nos, azt fogjuk mondani vagyunk, először is
Az összes, keresi az értéket 19.

75
00:03:20,620 --> 00:03:22,290
Megpróbáljuk megtalálni a 19-es szám.

76
00:03:22,290 --> 00:03:25,380
Az első elem az e
tömb található index nulla,

77
00:03:25,380 --> 00:03:28,880
és az utolsó eleme ennek
tömb található index 14.

78
00:03:28,880 --> 00:03:31,430
És így hívjuk azokat a kezdete és vége.

79
00:03:31,430 --> 00:03:35,387
>> Tehát kiszámítja a középpont által
hozzátéve 0 plusz 14 osztva 2;

80
00:03:35,387 --> 00:03:36,720
elég egyértelmű középpontját.

81
00:03:36,720 --> 00:03:40,190
És azt mondhatjuk, hogy
A középpont most 7.

82
00:03:40,190 --> 00:03:43,370
Tehát 15 amit keresett?

83
00:03:43,370 --> 00:03:43,940
Nem ez nem.

84
00:03:43,940 --> 00:03:45,270
Keresünk 19.

85
00:03:45,270 --> 00:03:49,400
De tudjuk, hogy 19 nagyobb
mint amit találtunk a közepén.

86
00:03:49,400 --> 00:03:52,470
>> Tehát mit tehetünk,
megváltoztatni a kezdőpont

87
00:03:52,470 --> 00:03:57,280
hogy csak a jobb oldalon a
középpontját, és ismételjük meg a folyamatot újra.

88
00:03:57,280 --> 00:04:01,690
És ha ezt tesszük, akkor most azt mondják, a
új kiindulási pont tömb helyen 8.

89
00:04:01,690 --> 00:04:07,220
Arra jöttünk hatékonyan tenni,
figyelmen kívül mindent balra 15.

90
00:04:07,220 --> 00:04:09,570
Végre megszabadultunk a fele
A probléma, és most,

91
00:04:09,570 --> 00:04:13,510
ahelyett, hogy keresni
Több mint 15 elem a tömbben,

92
00:04:13,510 --> 00:04:15,610
csak azt kell keresni több mint 7.

93
00:04:15,610 --> 00:04:17,706
Tehát 8 új kiindulási pontot.

94
00:04:17,706 --> 00:04:19,600
14 még mindig a végpontot.

95
00:04:19,600 --> 00:04:21,430
>> És most át megint.

96
00:04:21,430 --> 00:04:22,810
Kiszámítjuk az új középpontját.

97
00:04:22,810 --> 00:04:27,130
8 plusz 14 22, osztva 2-11.

98
00:04:27,130 --> 00:04:28,660
Ez az, amit keresünk?

99
00:04:28,660 --> 00:04:30,110
Nem ez nem.

100
00:04:30,110 --> 00:04:32,930
Keresünk egy értéket, ami
kevesebb, mint amit most találtam.

101
00:04:32,930 --> 00:04:34,721
Mi is így fogjuk megismételni
A folyamat újra.

102
00:04:34,721 --> 00:04:38,280
Fogunk változtatni a végpont
lehet csak a bal oldalon a középpont.

103
00:04:38,280 --> 00:04:41,800
Így az új végpont lesz 10.

104
00:04:41,800 --> 00:04:44,780
És most, hogy ez az egyetlen része
A tömb van kereshetőség.

105
00:04:44,780 --> 00:04:48,460
Tehát most már megszűnt
12 a 15 elemekkel.

106
00:04:48,460 --> 00:04:51,550
Tudjuk, hogy ha 19
létezik a tömbbel,

107
00:04:51,550 --> 00:04:57,210
léteznie kell valahol elem
száma 8 és elemszám 10.

108
00:04:57,210 --> 00:04:59,400
>> Tehát számítani az új középpontját újra.

109
00:04:59,400 --> 00:05:02,900
8 plusz 10 18, osztva 2-9.

110
00:05:02,900 --> 00:05:05,074
És ebben az esetben, nézd, a
cél a közepén.

111
00:05:05,074 --> 00:05:06,740
Találtunk pontosan mit is keresünk.

112
00:05:06,740 --> 00:05:07,780
Meg tudjuk állítani.

113
00:05:07,780 --> 00:05:10,561
Sikeresen befejeződött
bináris kereső.

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

115
00:05:11,060 --> 00:05:13,930
Tehát tudjuk, hogy ez az algoritmus
akkor működik, ha a cél

116
00:05:13,930 --> 00:05:16,070
valahol a tömb.

117
00:05:16,070 --> 00:05:19,060
Vajon ez az algoritmus munkát, ha
a cél nem a tömbben?

118
00:05:19,060 --> 00:05:20,810
Nos, kezdjük meg
újra, és ebben az időben,

119
00:05:20,810 --> 00:05:23,380
nézzük meg az elem
16, amely vizuálisan láthatjuk

120
00:05:23,380 --> 00:05:25,620
nem létezik sehol a tömbben.

121
00:05:25,620 --> 00:05:27,110
>> A kiindulási pont újra 0.

122
00:05:27,110 --> 00:05:28,590
A végpontot újra 14.

123
00:05:28,590 --> 00:05:32,490
Ezek az indexek az első és
utolsó elemei a teljes tömb.

124
00:05:32,490 --> 00:05:36,057
És akkor megy át a folyamat már csak
ment át újra, hogy kitalálja 16,

125
00:05:36,057 --> 00:05:39,140
még ha vizuálisan, akkor már
mondd, hogy ez nem lesz ott.

126
00:05:39,140 --> 00:05:43,450
Csak azt akarjuk, hogy győződjön meg arról, ez az algoritmus
majd, sőt, még mindig működik valamilyen módon

127
00:05:43,450 --> 00:05:46,310
és nem csak hagyja nekünk
beragadt egy végtelen ciklusban.

128
00:05:46,310 --> 00:05:48,190
>> Szóval mi a lépést az első?

129
00:05:48,190 --> 00:05:50,230
Számolja ki a középpont
A jelenlegi tömb.

130
00:05:50,230 --> 00:05:52,790
Mi a középpontját
A jelenlegi tömb?

131
00:05:52,790 --> 00:05:54,410
Nos, ez 7, ugye?

132
00:05:54,410 --> 00:05:57,560
14 plusz 0 osztva 2 7.

133
00:05:57,560 --> 00:05:59,280
15 amit keresett?

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

135
00:05:59,780 --> 00:06:02,930
Ez elég közel, de keressük
értéknél valamivel nagyobb annál.

136
00:06:02,930 --> 00:06:06,310
>> Tehát tudjuk, hogy ez meg fog
hová balra 15.

137
00:06:06,310 --> 00:06:08,540
A cél nagyobb, mint
mi van a középpont.

138
00:06:08,540 --> 00:06:12,450
És így meg az új kiindulási pont, hogy
lehet csak a jobb oldalon a középső.

139
00:06:12,450 --> 00:06:16,130
A felezőpontja jelenleg 7, így
mondjuk az új kezdőpont 8.

140
00:06:16,130 --> 00:06:18,130
És mi már hatékonyan
én ismét figyelmen kívül hagyja

141
00:06:18,130 --> 00:06:21,150
a teljes bal fele a tömbben.

142
00:06:21,150 --> 00:06:23,750
>> Most ismételje meg a
feldolgozására még egyszer.

143
00:06:23,750 --> 00:06:24,910
Számolja az új középpontját.

144
00:06:24,910 --> 00:06:29,350
8 plusz 14 22, osztva 2-11.

145
00:06:29,350 --> 00:06:31,060
23 amit keresett?

146
00:06:31,060 --> 00:06:31,870
Sajnos nincs.

147
00:06:31,870 --> 00:06:34,930
Keresünk egy értéket
amely kevesebb, mint 23.

148
00:06:34,930 --> 00:06:37,850
És így ebben az esetben, megyünk
változtatni a végpont, hogy csak

149
00:06:37,850 --> 00:06:40,035
hogy a bal oldalon a jelenlegi felezőpontja.

150
00:06:40,035 --> 00:06:43,440
A jelenlegi középpontját 11 és
így fogunk állítani az új végpont

151
00:06:43,440 --> 00:06:46,980
A következő alkalommal megyünk
ezen a folyamaton keresztül a 10.

152
00:06:46,980 --> 00:06:48,660
>> Ismét végig a folyamatot újra.

153
00:06:48,660 --> 00:06:49,640
Számolja ki a középpont.

154
00:06:49,640 --> 00:06:53,100
8 plusz 10 osztva 2 9.

155
00:06:53,100 --> 00:06:54,750
19 amit keresett?

156
00:06:54,750 --> 00:06:55,500
Sajnos nincs.

157
00:06:55,500 --> 00:06:58,050
Még mindig keresi
Számos kisebb.

158
00:06:58,050 --> 00:07:02,060
Így fogunk változtatni a végpontja ezúttal
hogy csak a bal oldalon a középpont.

159
00:07:02,060 --> 00:07:05,532
A középpont jelenleg 9,
így a végpont lesz 8.

160
00:07:05,532 --> 00:07:07,920
És most, átnézünk
egyetlen elem tömb.

161
00:07:07,920 --> 00:07:10,250
>> Mi a középpontját ez a tömb?

162
00:07:10,250 --> 00:07:13,459
Nos, indul 8, akkor
végződik 8, a középpont 8.

163
00:07:13,459 --> 00:07:14,750
Ez az, amit keresünk?

164
00:07:14,750 --> 00:07:16,339
Keresünk 17?

165
00:07:16,339 --> 00:07:17,380
Nem, keresünk 16.

166
00:07:17,380 --> 00:07:20,160
Tehát ha létezik a tömbben,
léteznie kell valahol

167
00:07:20,160 --> 00:07:21,935
balra, ahol jelenleg is.

168
00:07:21,935 --> 00:07:23,060
Szóval mit fogunk csinálni?

169
00:07:23,060 --> 00:07:26,610
Hát, majd adja meg a végpontot, hogy csak
hogy a bal oldalon a jelenlegi felezőpontja.

170
00:07:26,610 --> 00:07:29,055
Így fogunk változtatni a végpontja a 7.

171
00:07:29,055 --> 00:07:32,120
Látod, amit csak
történt itt, igaz?

172
00:07:32,120 --> 00:07:33,370
Nézz fel itt.

173
00:07:33,370 --> 00:07:35,970
>> Indítás most nagyobb, mint végéig.

174
00:07:35,970 --> 00:07:39,620
Hatékonyan, a két végét
a mi tömb átlépték,

175
00:07:39,620 --> 00:07:42,252
és a kiindulási pont
Most, miután a végpont.

176
00:07:42,252 --> 00:07:43,960
Nos, ez nem
semmi értelme, igaz?

177
00:07:43,960 --> 00:07:47,960
Tehát most, hogy mit tudunk mondani, mi
van egy al tömb mérete 0.

178
00:07:47,960 --> 00:07:50,110
És ha egyszer mi ütött
Ezen a ponton, mi most

179
00:07:50,110 --> 00:07:53,940
Garantáljuk, hogy 16 elem
nem létezik a tömbben,

180
00:07:53,940 --> 00:07:56,280
mert a kezdőpont
és végpontja keresztezték.

181
00:07:56,280 --> 00:07:58,340
És így már nincs ott.

182
00:07:58,340 --> 00:08:01,340
Most vegyük észre, hogy ez valamivel
más, mint a kiindulási pont és vége

183
00:08:01,340 --> 00:08:02,900
a pont jelentése azonos.

184
00:08:02,900 --> 00:08:05,030
Ha már keres
17, ez volna

185
00:08:05,030 --> 00:08:08,870
volt a tömbben, és a kezdőpont
és végpontja, hogy az utolsó iterációs

186
00:08:08,870 --> 00:08:11,820
mielőtt azokat a pontokat keresztbe,
azt találta volna 17 van.

187
00:08:11,820 --> 00:08:15,510
Csak amikor átkelnek, hogy mi lehet
Garantáljuk, hogy az elem nem

188
00:08:15,510 --> 00:08:17,180
létezzen a tömbben.

189
00:08:17,180 --> 00:08:20,260
>> Szóval vessünk egy csomó kevesebb
lépések, mint a lineáris keresést.

190
00:08:20,260 --> 00:08:23,250
A legrosszabb forgatókönyv esetén, mi volt
szétbontani egy listát az n elem

191
00:08:23,250 --> 00:08:27,770
többször félbe, hogy megtalálja a cél,
vagy azért, mert a cél elem

192
00:08:27,770 --> 00:08:33,110
lesz valahol az utolsó
osztály vagy nem is létezik egyáltalán.

193
00:08:33,110 --> 00:08:37,830
Tehát a legrosszabb esetben, meg kell
osszuk el a array-- tudod?

194
00:08:37,830 --> 00:08:40,510
Bejelentkezés n-szer; mi
kell vágni a problémát

195
00:08:40,510 --> 00:08:42,610
fél egy bizonyos számú alkalommal.

196
00:08:42,610 --> 00:08:45,160
Hogy több alkalommal is log n.

197
00:08:45,160 --> 00:08:46,510
>> Mi a legjobb esetben?

198
00:08:46,510 --> 00:08:48,899
Nos, az első alkalom,
kiszámítja a középpont,

199
00:08:48,899 --> 00:08:50,190
megtaláljuk, amit keresünk.

200
00:08:50,190 --> 00:08:52,150
Az összes előző
példák a bináris keresés

201
00:08:52,150 --> 00:08:55,489
most már csak ment át, ha volna
óta keresi a 15 elem,

202
00:08:55,489 --> 00:08:57,030
azt találta volna, hogy azonnal.

203
00:08:57,030 --> 00:08:58,321
Ez volt a kezdet kezdetén.

204
00:08:58,321 --> 00:09:01,200
Ez volt a középpontban,
Az első kísérlet egy osztott

205
00:09:01,200 --> 00:09:03,950
A szétválás bináris keresés.

206
00:09:03,950 --> 00:09:06,350
>> És így a legrosszabb
esetben bináris keresés fut

207
00:09:06,350 --> 00:09:11,580
a log n, ami lényegesen jobb,
mint a lineáris keresés, a legrosszabb esetben.

208
00:09:11,580 --> 00:09:16,210
A legjobb esetben, bináris
keresés fut omegája 1.

209
00:09:16,210 --> 00:09:18,990
Tehát bináris keresés is sok
jobb, mint a lineáris keresés,

210
00:09:18,990 --> 00:09:23,270
de meg kell foglalkozni a folyamat
válogatás a tömb első, mielőtt

211
00:09:23,270 --> 00:09:26,140
kihasználja az erejét bináris keresés.

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

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

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