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

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

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

4
00:00:06,220 --> 00:00:08,140
So ist eine binäre Suche
Algorithmus wir verwenden können,

5
00:00:08,140 --> 00:00:10,530
um ein Element innerhalb eines Arrays zu finden.

6
00:00:10,530 --> 00:00:14,710
Im Gegensatz zu linearen Suche erfordert es ein
Sonderbedingung vorher erfüllt werden,

7
00:00:14,710 --> 00:00:19,020
aber es ist so viel effizienter, wenn
Diese Voraussetzung ist in der Tat erfüllt.

8
00:00:19,020 --> 00:00:20,470
>> Also, was ist die Idee hier?

9
00:00:20,470 --> 00:00:21,780
es teile und herrsche.

10
00:00:21,780 --> 00:00:25,100
Wir wollen die Größe zu reduzieren
der Suchbereich um die Hälfte jeder Zeit

11
00:00:25,100 --> 00:00:27,240
um eine Zielnummer zu finden.

12
00:00:27,240 --> 00:00:29,520
Dies ist, wo diese Bedingung
kommt ins Spiel, wenn.

13
00:00:29,520 --> 00:00:32,740
Wir können nur die Macht der Hebelwirkung
Beseitigung Hälfte der Elemente

14
00:00:32,740 --> 00:00:36,070
ohne auch nur anzusehen
sie, wenn das Array sortiert.

15
00:00:36,070 --> 00:00:39,200
>> Wenn es ein komplettes Missverständnis,
Wir können nicht einfach aus der Hand

16
00:00:39,200 --> 00:00:42,870
verwerfen die Hälfte der Elemente, weil
wir wissen nicht, was wir zu verwerfen.

17
00:00:42,870 --> 00:00:45,624
Aber wenn das Array sortiert,
wir das tun können, weil wir

18
00:00:45,624 --> 00:00:48,040
wissen, dass alles, um die
links, wo wir Zeit sind

19
00:00:48,040 --> 00:00:50,500
muss niedriger sein als die sein,
Wert Wir sind momentan bei.

20
00:00:50,500 --> 00:00:52,300
Und alles rund um das
rechts, wo wir sind

21
00:00:52,300 --> 00:00:55,040
muß grßer sein als der Wert sein,
Wir willkommen im.

22
00:00:55,040 --> 00:00:58,710
>> Also, was ist der Pseudocode
Schritte für die binäre Suche?

23
00:00:58,710 --> 00:01:02,310
Wir wiederholen Sie diesen Vorgang, bis der
Array oder, wie wir durch gehen,

24
00:01:02,310 --> 00:01:07,740
Subarrays, kleinere Stücke
das Original-Array ist der Größe 0.

25
00:01:07,740 --> 00:01:10,960
Berechnen Sie den Mittelpunkt
des aktuellen Unterfeld.

26
00:01:10,960 --> 00:01:14,460
>> Wenn der Wert, den Sie suchen, ist
in diesem Element des Arrays, zu stoppen.

27
00:01:14,460 --> 00:01:15,030
Du hast es gefunden.

28
00:01:15,030 --> 00:01:16,550
Das ist großartig.

29
00:01:16,550 --> 00:01:19,610
Andernfalls, wenn das Ziel
weniger als das, was in der Mitte,

30
00:01:19,610 --> 00:01:23,430
so dass, wenn der Wert, den wir schauen,
für die niedriger ist als das, was wir sehen,

31
00:01:23,430 --> 00:01:26,780
Wiederholen Sie diesen Vorgang wieder, aber
ändern Sie den Endpunkt, statt

32
00:01:26,780 --> 00:01:29,300
des Seins das Original
Ergänzen vollständige Palette,

33
00:01:29,300 --> 00:01:34,110
nur auf der linken Seite sein,
von denen wir nur sah.

34
00:01:34,110 --> 00:01:38,940
>> Wir wussten, dass der mittlere war zu hoch,
oder das Ziel war weniger als die Mitte,

35
00:01:38,940 --> 00:01:42,210
und so muss sie vorhanden sind, wenn es
haupt existiert in dem Array,

36
00:01:42,210 --> 00:01:44,660
irgendwo links von der Mitte.

37
00:01:44,660 --> 00:01:48,120
Und so werden wir das Array gesetzt
Lage, nur nach links

38
00:01:48,120 --> 00:01:51,145
des Mittelpunkts als neuer Endpunkt.

39
00:01:51,145 --> 00:01:53,770
Umgekehrt, wenn sich das Ziel
mehr als das, was in der Mitte,

40
00:01:53,770 --> 00:01:55,750
wir genau das gleiche tun,
Prozess, sondern wir

41
00:01:55,750 --> 00:01:59,520
Ändern Sie den Startpunkt zu sein
gerade rechts von der Mitte

42
00:01:59,520 --> 00:02:00,680
wir gerade berechnet.

43
00:02:00,680 --> 00:02:03,220
Und dann, erneut zu beginnen wir den Prozess.

44
00:02:03,220 --> 00:02:05,220
>> Lassen Sie uns dies zu visualisieren, OK?

45
00:02:05,220 --> 00:02:08,620
Es gibt also eine Menge los und hier,
aber hier ist eine Anordnung der 15 Elemente.

46
00:02:08,620 --> 00:02:11,400
Und wir werden sein die Verfolgung
von viel mehr Sachen diesmal.

47
00:02:11,400 --> 00:02:13,870
So in lineare Suche waren wir
nur die Sorge um ein Ziel.

48
00:02:13,870 --> 00:02:15,869
Aber dieses Mal wollen wir
egal wo wir sind

49
00:02:15,869 --> 00:02:18,480
ab zu schauen, wo
halten wir suchen,

50
00:02:18,480 --> 00:02:21,876
und was ist der Mittelpunkt
des aktuellen Array.

51
00:02:21,876 --> 00:02:23,250
Also hier haben wir mit binären Suche zu gehen.

52
00:02:23,250 --> 00:02:25,290
Wir sind ziemlich gut zu gehen, nicht wahr?

53
00:02:25,290 --> 00:02:28,650
Ich werde einfach zu legen
hier unten eine Reihe von Indizes.

54
00:02:28,650 --> 00:02:32,430
Dies ist im Grunde nur, was Element
des Arrays wir reden.

55
00:02:32,430 --> 00:02:34,500
Mit linearer Suche, wir
kümmern, indem wir

56
00:02:34,500 --> 00:02:36,800
müssen wissen, wie viele
Elemente wir Iteration über,

57
00:02:36,800 --> 00:02:40,010
aber wir wissen nicht wirklich egal, was
Element, das wir willkommen im.

58
00:02:40,010 --> 00:02:41,014
In binären Suche, wir tun.

59
00:02:41,014 --> 00:02:42,930
Und so, die gerade sind
es als eine kleine Anleitung.

60
00:02:42,930 --> 00:02:44,910
>> So können wir anfangen, oder?

61
00:02:44,910 --> 00:02:46,240
Nun, nicht ganz.

62
00:02:46,240 --> 00:02:48,160
Denken Sie daran, was ich gesagt habe
über binäre Suche?

63
00:02:48,160 --> 00:02:50,955
Wir können es nicht auf eine
unsortierte Array oder anderes,

64
00:02:50,955 --> 00:02:55,820
wir nicht garantieren, dass die
bestimmte Elemente oder Werte nicht

65
00:02:55,820 --> 00:02:57,650
Versehen
verworfen, wenn wir einfach

66
00:02:57,650 --> 00:02:59,920
entscheiden Hälfte des Feldes ignorieren.

67
00:02:59,920 --> 00:03:02,574
>> So Schritt eins mit binäre Suche
ist, müssen Sie eine sortierte Array.

68
00:03:02,574 --> 00:03:05,240
Und Sie können jede der Sortier verwenden
Algorithmen, die wir gesprochen haben

69
00:03:05,240 --> 00:03:06,700
um Sie zu dieser Position zu bekommen.

70
00:03:06,700 --> 00:03:10,370
So, jetzt haben wir in einer Position, wo bist
wir binäre Suche durchführen.

71
00:03:10,370 --> 00:03:12,560
>> Lassen Sie uns also wiederholen Sie den Vorgang
Schritt für Schritt, und halten Sie

72
00:03:12,560 --> 00:03:14,830
verfolgen, was passiert, wie wir gehen.

73
00:03:14,830 --> 00:03:17,980
So ist der erste, was wir tun müssen ist, zu berechnen
der Mittelpunkt der aktuellen Array.

74
00:03:17,980 --> 00:03:20,620
Nun, wir werden sagen, wir sind in erster Linie
Alle, auf der Suche nach dem Wert 19.

75
00:03:20,620 --> 00:03:22,290
Wir versuchen, die Nummer 19 zu finden.

76
00:03:22,290 --> 00:03:25,380
Das erste Element dieser
Array bei Index Null liegt,

77
00:03:25,380 --> 00:03:28,880
und das letzte Element dieser
Array bei Index 14 entfernt.

78
00:03:28,880 --> 00:03:31,430
Und so werden wir diejenigen, Beginn und Ende nennen.

79
00:03:31,430 --> 00:03:35,387
>> So berechnen wir die Mittelpunkt durch
Hinzufügen 0 plus 14 geteilt durch 2;

80
00:03:35,387 --> 00:03:36,720
ziemlich einfach Mittelpunkt.

81
00:03:36,720 --> 00:03:40,190
Und wir können sagen, dass
der Mittelpunkt ist jetzt 7.

82
00:03:40,190 --> 00:03:43,370
So beträgt 15, was wir suchen?

83
00:03:43,370 --> 00:03:43,940
Nein, ist es nicht.

84
00:03:43,940 --> 00:03:45,270
Wir suchen nach 19 suchen.

85
00:03:45,270 --> 00:03:49,400
Aber wir wissen, dass 19 ist größer
als das, was wir in der Mitte gefunden.

86
00:03:49,400 --> 00:03:52,470
>> Also, was wir tun können, ist
Ändern Sie den Startpunkt

87
00:03:52,470 --> 00:03:57,280
nur auf der rechten Seite der Be
Mittelpunkt und wiederholen Sie den Vorgang.

88
00:03:57,280 --> 00:04:01,690
Und wenn wir das tun, haben wir jetzt sagen, dass die
neue Startpunkt ist Matrixort 8.

89
00:04:01,690 --> 00:04:07,220
Was wir getan haben, ist wirksam
ignoriert alles links von 15.

90
00:04:07,220 --> 00:04:09,570
Wir haben die Hälfte beseitigt
des Problems, und nun,

91
00:04:09,570 --> 00:04:13,510
anstatt zu suchen
mehr als 15 Elemente in unser Angebot,

92
00:04:13,510 --> 00:04:15,610
müssen wir nur über 7 zu suchen.

93
00:04:15,610 --> 00:04:17,706
So 8 ist der neue Startpunkt.

94
00:04:17,706 --> 00:04:19,600
14 ist noch der Endpunkt.

95
00:04:19,600 --> 00:04:21,430
>> Und nun, über diese gehen wir wieder.

96
00:04:21,430 --> 00:04:22,810
Wir berechnen den neuen Mittelpunkt.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 ist 22 geteilt durch 2 ist 11.

98
00:04:27,130 --> 00:04:28,660
Ist das, was wir suchen?

99
00:04:28,660 --> 00:04:30,110
Nein, ist es nicht.

100
00:04:30,110 --> 00:04:32,930
Wir suchen nach einem Wert, der ist auf der Suche
weniger als das, was wir gerade gefunden.

101
00:04:32,930 --> 00:04:34,721
So werden wir wiederholen
der Prozess erneut.

102
00:04:34,721 --> 00:04:38,280
Wir gehen, um den Endpunkt zu ändern
werden nur auf der linken Seite des Mittelpunktes.

103
00:04:38,280 --> 00:04:41,800
So ist die neue Endpunkt wird 10.

104
00:04:41,800 --> 00:04:44,780
Und jetzt, das ist der einzige Teil des
das Array haben wir zu sortieren.

105
00:04:44,780 --> 00:04:48,460
So haben wir nun beseitigt
12 der 15 Elemente.

106
00:04:48,460 --> 00:04:51,550
Wir wissen, dass, wenn 19
besteht in der Anordnung, es

107
00:04:51,550 --> 00:04:57,210
muss zwischen Element irgendwo vorhanden
Nummer 8 und Elementnummer 10.

108
00:04:57,210 --> 00:04:59,400
>> So berechnen wir erneut die neue Mittelpunkt.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 ist 18, dividiert durch 2 ist 9.

110
00:05:02,900 --> 00:05:05,074
Und in diesem Fall, schauen,
Ziel ist in der Mitte.

111
00:05:05,074 --> 00:05:06,740
Wir haben genau das, was wir suchen.

112
00:05:06,740 --> 00:05:07,780
Wir können aufhören.

113
00:05:07,780 --> 00:05:10,561
Wir erfolgreich abgeschlossen
eine binäre Suche.

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

115
00:05:11,060 --> 00:05:13,930
So wissen wir, diesen Algorithmus
arbeitet, wenn das Ziel

116
00:05:13,930 --> 00:05:16,070
irgendwo innerhalb des Arrays.

117
00:05:16,070 --> 00:05:19,060
Hat diesen Algorithmus Arbeit, wenn
das Ziel nicht in der Matrix?

118
00:05:19,060 --> 00:05:20,810
Nun, lasst uns starten
wieder, und diesmal

119
00:05:20,810 --> 00:05:23,380
schauen wir uns für das Element
16, die optisch können wir sehen,

120
00:05:23,380 --> 00:05:25,620
existiert nirgends in der Anordnung.

121
00:05:25,620 --> 00:05:27,110
>> Der Startpunkt ist wieder 0.

122
00:05:27,110 --> 00:05:28,590
Der Endpunkt ist wieder 14.

123
00:05:28,590 --> 00:05:32,490
Das sind die Indizes des ersten und
letzten Elemente des kompletten Arrays.

124
00:05:32,490 --> 00:05:36,057
Und wir werden durch den Prozess, den wir einfach gehen
ging durch wieder und versuchte, 16 zu finden,

125
00:05:36,057 --> 00:05:39,140
obwohl optisch können wir bereits
zu sagen, dass es nicht geht, dort zu sein.

126
00:05:39,140 --> 00:05:43,450
Wir wollen einfach nur sicher, diesen Algorithmus zu machen
wird in der Tat immer noch in irgendeiner Weise zu arbeiten

127
00:05:43,450 --> 00:05:46,310
und nicht nur lassen Sie uns
in einer Endlosschleife stecken.

128
00:05:46,310 --> 00:05:48,190
>> Also, was ist der Schritt ersten?

129
00:05:48,190 --> 00:05:50,230
Berechnen Sie den Mittelpunkt
des aktuellen Array.

130
00:05:50,230 --> 00:05:52,790
Was ist der Mittelpunkt
des aktuellen Array?

131
00:05:52,790 --> 00:05:54,410
Nun, es ist 7, oder?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 geteilt durch 2 ist 7.

133
00:05:57,560 --> 00:05:59,280
Ist 15, was wir suchen?

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

135
00:05:59,780 --> 00:06:02,930
Es ist ziemlich nahe, aber wir suchen
für einen Wert, der etwas größer als das.

136
00:06:02,930 --> 00:06:06,310
>> So wissen wir, dass es zu gehen
nirgends auf der linken Seite von 15.

137
00:06:06,310 --> 00:06:08,540
Das Ziel größer als
was ist in der Mitte.

138
00:06:08,540 --> 00:06:12,450
Und so setzen wir die neuen Startpunkt zu
werden direkt rechts von der Mitte.

139
00:06:12,450 --> 00:06:16,130
Der Mittelpunkt ist derzeit 7, so
sagen wir, der neue Startpunkt ist 8.

140
00:06:16,130 --> 00:06:18,130
Und was wir effektiv haben
wieder getan wird ignoriert

141
00:06:18,130 --> 00:06:21,150
die gesamte linke Hälfte der Anordnung.

142
00:06:21,150 --> 00:06:23,750
>> Jetzt wiederholen wir die
bearbeiten ein weiteres Mal.

143
00:06:23,750 --> 00:06:24,910
Berechnen Sie den neuen Mittelpunkt.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 ist 22 geteilt durch 2 ist 11.

145
00:06:29,350 --> 00:06:31,060
Ist 23, was wir suchen?

146
00:06:31,060 --> 00:06:31,870
Leider nein.

147
00:06:31,870 --> 00:06:34,930
Wir suchen nach einem Wert suchen
dh weniger als 23.

148
00:06:34,930 --> 00:06:37,850
Und so in diesem Fall, wir gehen
um den Endpunkt zu ändern, um nur sein,

149
00:06:37,850 --> 00:06:40,035
links von dem aktuellen Mittenpunkt.

150
00:06:40,035 --> 00:06:43,440
Der aktuelle Mittelpunkt ist 11, und
so werden wir den neuen Endpunkt zu setzen

151
00:06:43,440 --> 00:06:46,980
für das nächste Mal, wenn wir
durch diesen Prozess bis 10.

152
00:06:46,980 --> 00:06:48,660
>> Auch durch den Prozess gehen wir wieder.

153
00:06:48,660 --> 00:06:49,640
Berechnen Sie den Mittelpunkt.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 geteilt durch 2 ist 9.

155
00:06:53,100 --> 00:06:54,750
Ist 19, was wir suchen?

156
00:06:54,750 --> 00:06:55,500
Leider nein.

157
00:06:55,500 --> 00:06:58,050
Wir sind immer noch auf der Suche nach
eine Zahl kleiner als die.

158
00:06:58,050 --> 00:07:02,060
Also werden wir den Endpunkt dieses Mal ändern
nur auf der linken Seite des Mittelpunkts ist.

159
00:07:02,060 --> 00:07:05,532
Der Mittelpunkt ist derzeit 9,
so der Endpunkt wird 8 sein.

160
00:07:05,532 --> 00:07:07,920
Und jetzt sind wir gerade auf der Suche
an einem einzelnen Element-Array.

161
00:07:07,920 --> 00:07:10,250
>> Was ist der Mittelpunkt dieses Arrays?

162
00:07:10,250 --> 00:07:13,459
Nun, es beginnt bei 8, es
endet bei 8, der Mittelpunkt 8.

163
00:07:13,459 --> 00:07:14,750
Ist das, was wir suchen?

164
00:07:14,750 --> 00:07:16,339
Sind wir auf der Suche nach 17?

165
00:07:16,339 --> 00:07:17,380
Nein, wir für 16 suchen.

166
00:07:17,380 --> 00:07:20,160
So dass, wenn es in der Anordnung vorhanden ist,
es muss irgendwo vorhanden

167
00:07:20,160 --> 00:07:21,935
links von dem wir gegenwärtig sind.

168
00:07:21,935 --> 00:07:23,060
Also, was sollen wir tun?

169
00:07:23,060 --> 00:07:26,610
Nun, wir werden den Endpunkt setzen, gerecht zu sein
links von dem aktuellen Mittenpunkt.

170
00:07:26,610 --> 00:07:29,055
Also werden wir den Endpunkt bis 7 zu ändern.

171
00:07:29,055 --> 00:07:32,120
Wissen Sie, was gerade zu sehen
ist hier passiert, wenn?

172
00:07:32,120 --> 00:07:33,370
Schlagen Sie jetzt hier.

173
00:07:33,370 --> 00:07:35,970
>> Starten Sie jetzt größer als Ende.

174
00:07:35,970 --> 00:07:39,620
Wirksam, wobei die beiden Enden
der unser Angebot überquert haben,

175
00:07:39,620 --> 00:07:42,252
und der Startpunkt
Jetzt nach dem Endpunkt.

176
00:07:42,252 --> 00:07:43,960
Nun, das tut nicht
keinen Sinn, nicht wahr?

177
00:07:43,960 --> 00:07:47,960
So, jetzt, was wir sagen können ist, dass wir
eine Unter Array der Größe 0.

178
00:07:47,960 --> 00:07:50,110
Und wenn wir zu bekommen
Nun können wir uns jetzt

179
00:07:50,110 --> 00:07:53,940
garantieren, dass Element 16
nicht in der Matrix vorhanden sind,

180
00:07:53,940 --> 00:07:56,280
da der Startpunkt
und Endpunkt haben gekreuzt.

181
00:07:56,280 --> 00:07:58,340
Und so ist es nicht da.

182
00:07:58,340 --> 00:08:01,340
Nun beachtet, dass es sich leicht
anders als der Startpunkt und Ende

183
00:08:01,340 --> 00:08:02,900
weisen die gleiche ist.

184
00:08:02,900 --> 00:08:05,030
Wenn wir waren auf der Suche
für 17, müsste

185
00:08:05,030 --> 00:08:08,870
in der Anordnung, und der Startpunkt gewesen
und Endpunkt dieser letzten Iteration

186
00:08:08,870 --> 00:08:11,820
bevor diese Punkte überquerte,
würden wir dort gefunden haben 17.

187
00:08:11,820 --> 00:08:15,510
Es ist nur, wenn sie sich kreuzen, wir können
gewährleistet, dass das Element nicht

188
00:08:15,510 --> 00:08:17,180
existieren in der Anordnung.

189
00:08:17,180 --> 00:08:20,260
>> Werfen wir also viel weniger
Schritte als lineare Suche.

190
00:08:20,260 --> 00:08:23,250
Im schlimmsten Fall, wir hatten
zu zerlegen und eine Liste mit n Elementen

191
00:08:23,250 --> 00:08:27,770
mehrmals in der Mitte, um das Ziel zu finden,
entweder weil das Zielelement

192
00:08:27,770 --> 00:08:33,110
werden irgendwo in der letzte sein
Division oder es überhaupt nicht existieren.

193
00:08:33,110 --> 00:08:37,830
Also im ungünstigsten Fall müssen wir
spalten die array-- wissen Sie das?

194
00:08:37,830 --> 00:08:40,510
Log von n-mal; wir
haben, um das Problem zu schneiden

195
00:08:40,510 --> 00:08:42,610
Hälfte eine bestimmte Anzahl von Malen.

196
00:08:42,610 --> 00:08:45,160
Das Mal ist log n.

197
00:08:45,160 --> 00:08:46,510
>> Was ist der beste-Case-Szenario?

198
00:08:46,510 --> 00:08:48,899
Nun, das erste Mal,
Berechnung des Mittelpunkts,

199
00:08:48,899 --> 00:08:50,190
wir finden, was wir suchen.

200
00:08:50,190 --> 00:08:52,150
In allen vorherigen
Beispiele für binäre Suche

201
00:08:52,150 --> 00:08:55,489
wir haben etwas mehr gegangen, wenn wir
wurde für das Element 15 auf der Suche,

202
00:08:55,489 --> 00:08:57,030
wir würden das sofort gefunden.

203
00:08:57,030 --> 00:08:58,321
Das war ganz am Anfang.

204
00:08:58,321 --> 00:09:01,200
Das war der Mittelpunkt
der erste Versuch einer Spaltung

205
00:09:01,200 --> 00:09:03,950
einer Division in binäre Suche.

206
00:09:03,950 --> 00:09:06,350
>> Und so im schlimmsten
Fall binäre Suche läuft

207
00:09:06,350 --> 00:09:11,580
in log n, die wesentlich besser ist,
als lineare Suche, im schlimmsten Fall.

208
00:09:11,580 --> 00:09:16,210
Im besten Fall, binäre
Suche läuft an Omega von 1.

209
00:09:16,210 --> 00:09:18,990
So binäre Suche ist viel
besser als lineare Suche,

210
00:09:18,990 --> 00:09:23,270
aber Sie müssen mit dem Prozess der tun haben
Sortieren Sie Ihre Array zuerst, bevor Sie

211
00:09:23,270 --> 00:09:26,140
Nutzen Sie die Macht der binären Suche.

212
00:09:26,140 --> 00:09:27,130
>> Ich bin Doug Lloyd.

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

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