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

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Wszystko w porządku.

4
00:00:06,220 --> 00:00:08,140
Więc przeszukiwanie binarne jest
Algorytm możemy użyć

5
00:00:08,140 --> 00:00:10,530
znaleźć element wewnątrz tablicy.

6
00:00:10,530 --> 00:00:14,710
W przeciwieństwie do wyszukiwania liniowego, wymaga
być spełnione specjalne warunki wcześniej,

7
00:00:14,710 --> 00:00:19,020
ale jest o wiele bardziej efektywne, jeśli
warunek ten jest w rzeczywistości spełnione.

8
00:00:19,020 --> 00:00:20,470
>> Więc co to za pomysł tutaj?

9
00:00:20,470 --> 00:00:21,780
to dziel i rządź.

10
00:00:21,780 --> 00:00:25,100
Chcemy aby zmniejszyć rozmiar
obszar wyszukiwania o połowę za każdym razem

11
00:00:25,100 --> 00:00:27,240
W celu znalezienia numer docelowy.

12
00:00:27,240 --> 00:00:29,520
To jest, gdy warunek
wchodzi w grę, choć.

13
00:00:29,520 --> 00:00:32,740
Możemy jedynie wykorzystać moc
eliminując pół elementów

14
00:00:32,740 --> 00:00:36,070
nawet nie patrząc na
je jeśli tablica jest posortowana.

15
00:00:36,070 --> 00:00:39,200
>> Jeśli jest to kompletne zamieszanie,
Nie możemy po prostu z ręki

16
00:00:39,200 --> 00:00:42,870
usunięcia połowy elementów, ponieważ
nie wiemy, z czym mamy do odrzucenia.

17
00:00:42,870 --> 00:00:45,624
Ale jeśli tablica jest posortowana,
możemy to zrobić, bo

18
00:00:45,624 --> 00:00:48,040
wiem, że wszystko, co do
lewej, gdzie obecnie są

19
00:00:48,040 --> 00:00:50,500
musi być niższa niż
Wartość jesteśmy obecnie.

20
00:00:50,500 --> 00:00:52,300
I wszystko, co do
Prawo gdzie jesteśmy

21
00:00:52,300 --> 00:00:55,040
musi być większa niż wartość
jesteśmy obecnie patrząc na.

22
00:00:55,040 --> 00:00:58,710
>> Więc co jest pseudokod
Kroki wyszukiwania binarnego?

23
00:00:58,710 --> 00:01:02,310
Powtarzamy ten proces do czasu
tablica lub, jak przejść przez,

24
00:01:02,310 --> 00:01:07,740
sub tablice, mniejsze kawałki
oryginalna tablica, jest od wielkości 0.

25
00:01:07,740 --> 00:01:10,960
Oblicz punkt środkowy
bieżącej tablicy pomocniczej.

26
00:01:10,960 --> 00:01:14,460
>> Jeśli wartość szukasz jest
w tym elemencie tablicy, stop.

27
00:01:14,460 --> 00:01:15,030
Znalazłeś to.

28
00:01:15,030 --> 00:01:16,550
To wspaniale.

29
00:01:16,550 --> 00:01:19,610
W przeciwnym razie, jeśli celem jest
mniej niż to, co jest w środku,

30
00:01:19,610 --> 00:01:23,430
więc jeśli wartości szukamy
na jest niższa niż to, co widzimy,

31
00:01:23,430 --> 00:01:26,780
powtórzyć ten proces ponownie, ale
zmienić punkt końcowy, zamiast

32
00:01:26,780 --> 00:01:29,300
bycia oryginalny
wykonać pełny zakres,

33
00:01:29,300 --> 00:01:34,110
się na lewo
od tego, gdzie właśnie wyglądało.

34
00:01:34,110 --> 00:01:38,940
>> Wiedzieliśmy, że w środku była zbyt wysoka,
lub celem było mniej niż w połowie,

35
00:01:38,940 --> 00:01:42,210
a więc musi istnieć, jeśli to
ogóle istnieje w tablicy

36
00:01:42,210 --> 00:01:44,660
gdzie z lewej strony środkowego.

37
00:01:44,660 --> 00:01:48,120
I tak będziemy ustawić tablicę
lokalizacja tuż na lewo

38
00:01:48,120 --> 00:01:51,145
punktu środkowego jako nowego punktu końcowego.

39
00:01:51,145 --> 00:01:53,770
Z drugiej strony, jeśli celem jest
większa niż to, co jest w środku,

40
00:01:53,770 --> 00:01:55,750
robimy dokładnie to samo
Proces, ale zamiast tego

41
00:01:55,750 --> 00:01:59,520
zmienić punkt początkowy będzie
na prawo od punktu środkowego

42
00:01:59,520 --> 00:02:00,680
po prostu obliczyć.

43
00:02:00,680 --> 00:02:03,220
A potem zaczynamy kolejny proces.

44
00:02:03,220 --> 00:02:05,220
>> Powiedzmy, wizualizować to, OK?

45
00:02:05,220 --> 00:02:08,620
Więc nie wiele się dzieje, a tu,
ale tu jest tablica z 15 elementów.

46
00:02:08,620 --> 00:02:11,400
I mamy zamiar być śledzenie
o wiele więcej rzeczy w tym czasie.

47
00:02:11,400 --> 00:02:13,870
Tak więc w poszukiwaniu liniowego, byliśmy
po prostu dbanie o cel.

48
00:02:13,870 --> 00:02:15,869
Ale tym razem chcemy
dbać o tym, gdzie jesteśmy

49
00:02:15,869 --> 00:02:18,480
zaczyna wyglądać, gdzie
się zatrzymujemy, patrząc,

50
00:02:18,480 --> 00:02:21,876
i co to jest punkt środkowy
bieżącej tablicy.

51
00:02:21,876 --> 00:02:23,250
Więc zaczynamy z wyszukiwaniem binarnym.

52
00:02:23,250 --> 00:02:25,290
Jesteśmy prawie dobrze iść, prawda?

53
00:02:25,290 --> 00:02:28,650
Idę do wysadzenia
poniżej tutaj zestaw wskaźników.

54
00:02:28,650 --> 00:02:32,430
Jest to w zasadzie tylko to, co elementem
tablicy mówimy.

55
00:02:32,430 --> 00:02:34,500
Przy poszukiwaniu liniowego, mamy
obchodzi, ponieważ my

56
00:02:34,500 --> 00:02:36,800
trzeba wiedzieć, jak wiele
Elementy mamy iteracji po,

57
00:02:36,800 --> 00:02:40,010
ale w rzeczywistości nie obchodzi, co
Element jesteśmy obecnie patrząc na.

58
00:02:40,010 --> 00:02:41,014
W poszukiwaniu binarnego, co robimy.

59
00:02:41,014 --> 00:02:42,930
A tak, to są po prostu
nie jako mały przewodnik.

60
00:02:42,930 --> 00:02:44,910
>> Więc możemy zacząć, prawda?

61
00:02:44,910 --> 00:02:46,240
No, nie całkiem.

62
00:02:46,240 --> 00:02:48,160
Pamiętaj, co powiedziałem
o poszukiwaniu binarnym?

63
00:02:48,160 --> 00:02:50,955
Nie możemy tego zrobić na zasadzie
nieposortowane tablicą lub innego,

64
00:02:50,955 --> 00:02:55,820
nie gwarantują, że
pewne elementy lub wartości nie są

65
00:02:55,820 --> 00:02:57,650
przypadkowym
wyrzucić, kiedy tylko

66
00:02:57,650 --> 00:02:59,920
zignorować połowę tablicy.

67
00:02:59,920 --> 00:03:02,574
>> Więc kroku z wyszukiwaniem binarnym
to trzeba mieć posortowaną tablicę.

68
00:03:02,574 --> 00:03:05,240
I można użyć dowolnego z sortowania
Algorytmy Mówiliśmy o

69
00:03:05,240 --> 00:03:06,700
aby dostać się do tej pozycji.

70
00:03:06,700 --> 00:03:10,370
Więc teraz, że jesteśmy w miejscu, gdzie
możemy wykonać wyszukiwanie binarne.

71
00:03:10,370 --> 00:03:12,560
>> Warto więc powtórzyć proces
krok po kroku i zachować

72
00:03:12,560 --> 00:03:14,830
utwór z tego, co się dzieje, jak idziemy.

73
00:03:14,830 --> 00:03:17,980
Więc pierwsze co musimy zrobić to obliczyć
punkt środkowy aktualnej tablicy.

74
00:03:17,980 --> 00:03:20,620
Cóż, to mówimy, że jesteśmy przede
wszystkim, patrząc na wartość 19.

75
00:03:20,620 --> 00:03:22,290
Próbujemy znaleźć numer 19.

76
00:03:22,290 --> 00:03:25,380
Pierwszy element to
Tablica znajduje się na indeksie zerowym,

77
00:03:25,380 --> 00:03:28,880
i ostatnim elementem tego
Tablica znajduje się na indeks 14.

78
00:03:28,880 --> 00:03:31,430
I tak będziemy nazywać te początek i koniec.

79
00:03:31,430 --> 00:03:35,387
>> Tak więc obliczyć punkt środkowy przez
dodanie 0 plusa 14 podzielone przez 2;

80
00:03:35,387 --> 00:03:36,720
bardzo proste punkt środkowy.

81
00:03:36,720 --> 00:03:40,190
I można powiedzieć, że
punkt środkowy jest obecnie 7.

82
00:03:40,190 --> 00:03:43,370
Więc jest 15, co szukasz?

83
00:03:43,370 --> 00:03:43,940
Nie, nie jest.

84
00:03:43,940 --> 00:03:45,270
Szukamy 19.

85
00:03:45,270 --> 00:03:49,400
Ale wiemy, że 19 jest większa
niż to, co znaleźliśmy w środku.

86
00:03:49,400 --> 00:03:52,470
>> Więc co możemy zrobić, to
zmienić punkt początkowy

87
00:03:52,470 --> 00:03:57,280
się na prawo z
punkt środkowy, i ponownie powtórzyć proces.

88
00:03:57,280 --> 00:04:01,690
A kiedy to zrobimy, możemy teraz powiedzieć
Nowy punkt początkowy jest lokalizacja tablicy 8.

89
00:04:01,690 --> 00:04:07,220
Co mamy skutecznie wykonywane jest
ignorowane wszystko z lewej 15.

90
00:04:07,220 --> 00:04:09,570
Usunęliśmy połowę
problemu, a teraz,

91
00:04:09,570 --> 00:04:13,510
Zamiast konieczności wyszukiwania
ponad 15 elementy w naszej tablicy,

92
00:04:13,510 --> 00:04:15,610
mamy tylko przeszukiwać 7.

93
00:04:15,610 --> 00:04:17,706
Więc 8 to nowy punkt początkowy.

94
00:04:17,706 --> 00:04:19,600
14 nadal jest punktem końcowym.

95
00:04:19,600 --> 00:04:21,430
>> A teraz idziemy na to jeszcze raz.

96
00:04:21,430 --> 00:04:22,810
Obliczamy nowy punkt środkowy.

97
00:04:22,810 --> 00:04:27,130
8 oraz 14 jest 22, dzieli się przez 2 jest 11.

98
00:04:27,130 --> 00:04:28,660
Czy to, co szukasz?

99
00:04:28,660 --> 00:04:30,110
Nie, nie jest.

100
00:04:30,110 --> 00:04:32,930
Szukamy wartości, który jest
mniej niż to, co po prostu znaleźć.

101
00:04:32,930 --> 00:04:34,721
Tak więc mamy zamiar powtórzyć
kolejny proces.

102
00:04:34,721 --> 00:04:38,280
Mamy zamiar zmienić punkt końcowy do
się na lewo od punktu środkowego.

103
00:04:38,280 --> 00:04:41,800
Tak więc nowy punkt końcowy staje się 10.

104
00:04:41,800 --> 00:04:44,780
I teraz, że to tylko część
tablica mamy do sortowania.

105
00:04:44,780 --> 00:04:48,460
Więc mamy teraz wyeliminowane
12 z 15 elementów.

106
00:04:48,460 --> 00:04:51,550
Wiemy, że jeśli 19
istnieje w tablicy, to

107
00:04:51,550 --> 00:04:57,210
musi istnieć gdzieś pomiędzy elementem
Element numer 8 i numer 10.

108
00:04:57,210 --> 00:04:59,400
>> Tak więc obliczyć nowy punkt środkowy ponownie.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 jest 18, dzieli się przez 2 9.

110
00:05:02,900 --> 00:05:05,074
I w tym przypadku, wygląd,
cel jest w środku.

111
00:05:05,074 --> 00:05:06,740
Znaleźliśmy dokładnie to, czego szukasz.

112
00:05:06,740 --> 00:05:07,780
Mozemy przestac.

113
00:05:07,780 --> 00:05:10,561
Z powodzeniem zakończone
binarny wyszukiwania.

114
00:05:10,561 --> 00:05:11,060
W porządku.

115
00:05:11,060 --> 00:05:13,930
Więc wiemy tego algorytmu
działa, jeśli cel jest

116
00:05:13,930 --> 00:05:16,070
gdzieś w środku tablicy.

117
00:05:16,070 --> 00:05:19,060
To działa algorytm jeśli
cel nie znajduje się w tablicy?

118
00:05:19,060 --> 00:05:20,810
Cóż, zacznijmy go
ponownie i tym razem,

119
00:05:20,810 --> 00:05:23,380
spójrzmy na elemencie
16, które wizualnie możemy zobaczyć

120
00:05:23,380 --> 00:05:25,620
nie występują wszędzie w tablicy.

121
00:05:25,620 --> 00:05:27,110
>> Punkt początkowy jest znowu 0.

122
00:05:27,110 --> 00:05:28,590
Punkt końcowy jest jeszcze 14.

123
00:05:28,590 --> 00:05:32,490
Są to wskaźniki pierwszego i
ostatnie elementy kompletnej tablicy.

124
00:05:32,490 --> 00:05:36,057
A my przejść przez proces po prostu
ponownie przeszedł, starając się znaleźć 16,

125
00:05:36,057 --> 00:05:39,140
chociaż wizualnie, już możliwe
powiedzieć, że to nie będzie tam być.

126
00:05:39,140 --> 00:05:43,450
Chcemy tylko, aby upewnić się, że ten algorytm
będzie w rzeczywistości nadal pracują w sposób

127
00:05:43,450 --> 00:05:46,310
a nie tylko zostawić nas
utknąć w nieskończonej pętli.

128
00:05:46,310 --> 00:05:48,190
>> Więc co jest krokiem w pierwszej kolejności?

129
00:05:48,190 --> 00:05:50,230
Oblicz punkt środkowy
bieżącej tablicy.

130
00:05:50,230 --> 00:05:52,790
Co znajduje się punkt środkowy
bieżącej tablicy?

131
00:05:52,790 --> 00:05:54,410
Cóż, jest to 7, prawda?

132
00:05:54,410 --> 00:05:57,560
14 oraz 0 podzielone przez 2 to 7.

133
00:05:57,560 --> 00:05:59,280
Jest 15, co szukasz?

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

135
00:05:59,780 --> 00:06:02,930
Jest to dość blisko, ale szukamy
o wartości nieznacznie większej niż.

136
00:06:02,930 --> 00:06:06,310
>> Wiemy, że to będzie
mieć nigdzie w lewo 15.

137
00:06:06,310 --> 00:06:08,540
Docelowa jest większa niż
co jest w punkcie środkowym.

138
00:06:08,540 --> 00:06:12,450
I tak ustawić nowy punkt początkowy do
się na prawo od środka.

139
00:06:12,450 --> 00:06:16,130
Punkt środkowy jest obecnie 7, więc
powiedzmy, że nowy punkt początkowy jest 8.

140
00:06:16,130 --> 00:06:18,130
A co skutecznie mam
wykonane ponownie jest ignorowany

141
00:06:18,130 --> 00:06:21,150
cała lewa połowa macierzy.

142
00:06:21,150 --> 00:06:23,750
>> Teraz powtórz
proces jeszcze raz.

143
00:06:23,750 --> 00:06:24,910
Oblicz nowy punkt środkowy.

144
00:06:24,910 --> 00:06:29,350
8 oraz 14 jest 22, dzieli się przez 2 jest 11.

145
00:06:29,350 --> 00:06:31,060
Jest 23, co szukasz?

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

147
00:06:31,870 --> 00:06:34,930
Szukamy wartości
która jest mniejsza niż 23.

148
00:06:34,930 --> 00:06:37,850
I tak w tym przypadku, będziemy
zmienić punkt końcowy, który jest po prostu

149
00:06:37,850 --> 00:06:40,035
w lewo bieżącego punktu środkowego.

150
00:06:40,035 --> 00:06:43,440
Obecny punkt środkowy jest 11, a
więc będziemy ustawić nowy punkt końcowy

151
00:06:43,440 --> 00:06:46,980
następnym razem idziemy
w tym procesie do 10.

152
00:06:46,980 --> 00:06:48,660
>> Ponownie przejść przez proces ponownie.

153
00:06:48,660 --> 00:06:49,640
Oblicz punkt środkowy.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 podzielone przez 2 to 9.

155
00:06:53,100 --> 00:06:54,750
Jest 19, co szukasz?

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

157
00:06:55,500 --> 00:06:58,050
Wciąż szukasz
wiele mniej.

158
00:06:58,050 --> 00:07:02,060
Będziemy więc zmienić punkt końcowy, tym razem
się na lewo od punktu środkowego.

159
00:07:02,060 --> 00:07:05,532
Punkt środkowy jest obecnie 9,
więc punkt końcowy będzie 8.

160
00:07:05,532 --> 00:07:07,920
A teraz, po prostu patrząc
w jednym elemencie tablicy.

161
00:07:07,920 --> 00:07:10,250
>> Co znajduje się punkt środkowy tej tablicy?

162
00:07:10,250 --> 00:07:13,459
Cóż, to zaczyna się o 8, to
kończy się na 8, punkt środkowy jest 8.

163
00:07:13,459 --> 00:07:14,750
Czy to jest to, czego szukasz?

164
00:07:14,750 --> 00:07:16,339
Szukamy 17?

165
00:07:16,339 --> 00:07:17,380
Nie, szukamy 16.

166
00:07:17,380 --> 00:07:20,160
Tak więc, jeżeli istnieje w tablicy
musi gdzieś istnieć

167
00:07:20,160 --> 00:07:21,935
z lewej strony w którym aktualnie jesteśmy.

168
00:07:21,935 --> 00:07:23,060
Więc co zrobimy?

169
00:07:23,060 --> 00:07:26,610
Cóż, ustawić punkt końcowy, aby być tylko
w lewo bieżącego punktu środkowego.

170
00:07:26,610 --> 00:07:29,055
Będziemy więc zmienić punkt końcowy do 7.

171
00:07:29,055 --> 00:07:32,120
Czy widzisz, co się
tu się stało, chociaż?

172
00:07:32,120 --> 00:07:33,370
Spójrz tutaj.

173
00:07:33,370 --> 00:07:35,970
>> Start jest teraz większa niż koniec.

174
00:07:35,970 --> 00:07:39,620
W efekcie, obydwa końce
naszej tablicy są skrzyżowane,

175
00:07:39,620 --> 00:07:42,252
i punkt startu
Teraz, po punkcie końcowym.

176
00:07:42,252 --> 00:07:43,960
Dobrze, że nie
żadnego sensu, prawda?

177
00:07:43,960 --> 00:07:47,960
Więc teraz, co możemy powiedzieć, to to, że
mają sub wachlarz wielkości 0.

178
00:07:47,960 --> 00:07:50,110
A kiedy mamy zdobyć się
ten punkt, możemy teraz

179
00:07:50,110 --> 00:07:53,940
Gwarantujemy ten element 16
nie istnieje w tablicy

180
00:07:53,940 --> 00:07:56,280
Ponieważ punkt startu
i punkt końcowy przekroczyły.

181
00:07:56,280 --> 00:07:58,340
I tak go nie ma.

182
00:07:58,340 --> 00:08:01,340
Teraz zwróć uwagę, że jest to nieco
różni się od punktu startu i końca

183
00:08:01,340 --> 00:08:02,900
punkt znajduje się taka sama.

184
00:08:02,900 --> 00:08:05,030
Gdybyśmy byli patrząc
na 17, to mają

185
00:08:05,030 --> 00:08:08,870
było w tablicy, a punktem startowym
i punkt końcowy tej ostatniej iteracji

186
00:08:08,870 --> 00:08:11,820
zanim te punkty skrzyżowane,
znaleźlibyśmy 17 tam.

187
00:08:11,820 --> 00:08:15,510
To tylko wtedy, gdy przekraczają one, że możemy
Gwarantujemy, że element nie

188
00:08:15,510 --> 00:08:17,180
istnieje w tablicy.

189
00:08:17,180 --> 00:08:20,260
>> Warto więc o wiele mniej
kroków niż wyszukiwania liniowego.

190
00:08:20,260 --> 00:08:23,250
W najgorszym przypadku, mieliśmy
podzielić listę n elementów

191
00:08:23,250 --> 00:08:27,770
wielokrotnie w połowie, aby znaleźć cel,
albo dlatego, że element docelowy

192
00:08:27,770 --> 00:08:33,110
będzie gdzieś w ostatni
Podział lub nie istnieją w ogóle.

193
00:08:33,110 --> 00:08:37,830
Tak więc w najgorszym przypadku, mamy do
podzielone na array-- wiesz?

194
00:08:37,830 --> 00:08:40,510
Log n razy; my
trzeba wyciąć problem

195
00:08:40,510 --> 00:08:42,610
w pół pewną liczbę razy.

196
00:08:42,610 --> 00:08:45,160
To ile razy jest log n.

197
00:08:45,160 --> 00:08:46,510
>> Jaki jest najlepszy scenariusz?

198
00:08:46,510 --> 00:08:48,899
Cóż, pierwszy razem
obliczyć punkt środkowy,

199
00:08:48,899 --> 00:08:50,190
możemy znaleźć to, czego szukamy.

200
00:08:50,190 --> 00:08:52,150
W sumie poprzedni
przykłady dotyczące wyszukiwania binarnego

201
00:08:52,150 --> 00:08:55,489
my właśnie przeszedł, gdybyśmy mieli
szukamy elementu 15,

202
00:08:55,489 --> 00:08:57,030
nie stwierdzono, że natychmiast.

203
00:08:57,030 --> 00:08:58,321
To było na samym początku.

204
00:08:58,321 --> 00:09:01,200
To był punkt środkowy
pierwsza próba podziału

205
00:09:01,200 --> 00:09:03,950
dywizji w poszukiwaniu binarnym.

206
00:09:03,950 --> 00:09:06,350
>> I tak w najgorszym
Sprawa, wyszukiwania binarnego działa

207
00:09:06,350 --> 00:09:11,580
w log n, która jest znacznie lepsza
niż poszukiwanie liniowej, w najgorszym przypadku.

208
00:09:11,580 --> 00:09:16,210
W najlepszym przypadku, binarny
Wyszukiwarka działa w omega 1.

209
00:09:16,210 --> 00:09:18,990
Więc przeszukiwanie binarne jest dużo
lepiej niż wyszukiwania liniowego,

210
00:09:18,990 --> 00:09:23,270
ale masz do czynienia z procesem
sortowanie swoją tablicę zanim można

211
00:09:23,270 --> 00:09:26,140
wykorzystać możliwości wyszukiwania binarnego.

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

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

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