1
00:00:00,000 --> 00:00:03,346
>> [MUSIC PLAYING]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Bütün hüququ.

4
00:00:06,220 --> 00:00:08,140
Belə ki, ikili axtarış bir deyil
biz istifadə edə bilərsiniz alqoritm

5
00:00:08,140 --> 00:00:10,530
bir sıra daxili bir element tapa bilərsiniz.

6
00:00:10,530 --> 00:00:14,710
Xətti axtarış fərqli olaraq, tələb
xüsusi şərt əvvəlcədən görüşüb

7
00:00:14,710 --> 00:00:19,020
lakin bu çox daha çox səmərəli əgər var
şərtdir ki, əslində, bir araya gəldi.

8
00:00:19,020 --> 00:00:20,470
>> Belə ki, fikir burada nə var?

9
00:00:20,470 --> 00:00:21,780
Bu bölmək və fəth edir.

10
00:00:21,780 --> 00:00:25,100
Biz ölçüsünü azaltmaq istəyirəm
yarım hər vaxt Axtarış sahəsi

11
00:00:25,100 --> 00:00:27,240
bir hədəf sayı tapmaq üçün.

12
00:00:27,240 --> 00:00:29,520
Bu harada vəziyyəti
baxmayaraq ki, dövrəyə girir.

13
00:00:29,520 --> 00:00:32,740
Biz yalnız güc leverage
elementləri aradan qaldırılması yarım

14
00:00:32,740 --> 00:00:36,070
hətta baxmadan
Onlara array çeşidlənir əgər.

15
00:00:36,070 --> 00:00:39,200
>> Tam bir mix var varsa,
biz yalnız əl həyata bilməz

16
00:00:39,200 --> 00:00:42,870
Çünki elementlərin yarım imtina
biz discarding nə bilmirəm.

17
00:00:42,870 --> 00:00:45,624
Amma array sıralanır əgər
biz bunu edə bilərsiniz, çünki biz

18
00:00:45,624 --> 00:00:48,040
ki, hər şeyi bilmək
Hal-hazırda burada sol

19
00:00:48,040 --> 00:00:50,500
daha aşağı olmalıdır
dəyəri Hal-hazırda istəyirik.

20
00:00:50,500 --> 00:00:52,300
Və hər şey üçün
Biz harada hüququ

21
00:00:52,300 --> 00:00:55,040
dəyəri daha böyük olmalıdır
Hal-hazırda baxırıq.

22
00:00:55,040 --> 00:00:58,710
>> Belə ki, pseudocode nə
Binar axtarış üçün addımlar?

23
00:00:58,710 --> 00:01:02,310
Biz qədər bu prosesi təkrar
array və ya, biz vasitəsilə davam kimi,

24
00:01:02,310 --> 00:01:07,740
sub Diziler, kiçik ədəd
orijinal array ölçüsü 0 var.

25
00:01:07,740 --> 00:01:10,960
Orta hesablayın
Cari sub serialın.

26
00:01:10,960 --> 00:01:14,460
>> Aradığınız dəyəri əgər
array ki element, dayandırmaq.

27
00:01:14,460 --> 00:01:15,030
Siz tapdı.

28
00:01:15,030 --> 00:01:16,550
Bu əladır.

29
00:01:16,550 --> 00:01:19,610
Əks halda, hədəf əgər
orta nə az,

30
00:01:19,610 --> 00:01:23,430
belə dəyər əgər biz aradığınız
, biz görmək nə aşağı

31
00:01:23,430 --> 00:01:26,780
yenidən bu prosesi təkrar, lakin
əvəzinə, son nöqtəsi dəyişə

32
00:01:26,780 --> 00:01:29,300
orijinal olan
tam array tam,

33
00:01:29,300 --> 00:01:34,110
yalnız sol olmaq
harada biz yalnız baxdı.

34
00:01:34,110 --> 00:01:38,940
>> Biz orta çox yüksək idi ki, bilirdi
və ya hədəf, orta az idi

35
00:01:38,940 --> 00:01:42,210
və belə ki, mövcud olmalıdır bu əgər
, bütün array var

36
00:01:42,210 --> 00:01:44,660
haradasa orta sol.

37
00:01:44,660 --> 00:01:48,120
Və belə ki, biz array qurmaq lazımdır
yalnız sol yer

38
00:01:48,120 --> 00:01:51,145
yeni bitmə nöqtəsinə kimi orta edir.

39
00:01:51,145 --> 00:01:53,770
Əksinə, hədəf əgər
orta nə daha çox,

40
00:01:53,770 --> 00:01:55,750
biz eyni edə
proses, lakin əvəzinə biz

41
00:01:55,750 --> 00:01:59,520
olmaq başlanğıc nöqtəsi dəyişdirmək
yalnız orta sağ üçün

42
00:01:59,520 --> 00:02:00,680
biz yalnız hesablanır.

43
00:02:00,680 --> 00:02:03,220
Və sonra, biz yenə prosesi başlayır.

44
00:02:03,220 --> 00:02:05,220
>> OK, bu görüntüləmək edək?

45
00:02:05,220 --> 00:02:08,620
Belə ki, davam və burada bir çox var,
lakin burada 15 elementlər bir sıra var.

46
00:02:08,620 --> 00:02:11,400
Və biz takip saxlanılması olacaq
daha çox şeylər bu dəfə.

47
00:02:11,400 --> 00:02:13,870
Belə ki, xətti axtarış, biz
yalnız bir hədəf haqqında qayğı.

48
00:02:13,870 --> 00:02:15,869
Amma bu dəfə istəyirik
Biz harada qayğı

49
00:02:15,869 --> 00:02:18,480
baxmaq başlayır, harada
biz axtarır dayandırılması olunur,

50
00:02:18,480 --> 00:02:21,876
və orta nə
cari serialın.

51
00:02:21,876 --> 00:02:23,250
Belə ki, burada biz ikili axtarış gedin.

52
00:02:23,250 --> 00:02:25,290
Biz olduqca çox yaxşı getmək, sağ istəyirik?

53
00:02:25,290 --> 00:02:28,650
Mən yalnız yazmaq üçün gedirəm
indeksləri bir sıra aşağıda və burada.

54
00:02:28,650 --> 00:02:32,430
Bu əsasən yalnız nə elementidir
serialın bəhs edirik.

55
00:02:32,430 --> 00:02:34,500
Xətti axtarış, biz
biz kimi İsa qayğı

56
00:02:34,500 --> 00:02:36,800
neçə bilmək lazımdır
biz artıq iterating edirik elementləri,

57
00:02:36,800 --> 00:02:40,010
lakin biz, həqiqətən, qayğı yoxdur nə
element Hal-hazırda baxırıq.

58
00:02:40,010 --> 00:02:41,014
Ikili axtarış, edirik.

59
00:02:41,014 --> 00:02:42,930
Və belə ki, o, yalnız var
bir az bələdçi kimi.

60
00:02:42,930 --> 00:02:44,910
>> Beləliklə, biz sağ, başlaya bilərsiniz?

61
00:02:44,910 --> 00:02:46,240
Bəli, tamamilə.

62
00:02:46,240 --> 00:02:48,160
Dedim nə saxla
ikili axtarış haqqında?

63
00:02:48,160 --> 00:02:50,955
Biz bunu edə bilməz
başqa çeşidlənməmiş array və ya,

64
00:02:50,955 --> 00:02:55,820
ki, təmin deyil
Müəyyən elementləri və ya dəyərlər deyil

65
00:02:55,820 --> 00:02:57,650
təsadüfən olan
atılır zaman biz yalnız

66
00:02:57,650 --> 00:02:59,920
serialın yarısı ignore qərar.

67
00:02:59,920 --> 00:03:02,574
>> Belə ki, ikili axtarış ilə bir addım
Bir sıralanır array olmalıdır edir.

68
00:03:02,574 --> 00:03:05,240
Və çeşidlənməsi hər hansı bir istifadə edə bilərsiniz
Biz haqqında söhbət etdik alqoritmlər

69
00:03:05,240 --> 00:03:06,700
ki, mövqe almaq üçün.

70
00:03:06,700 --> 00:03:10,370
Belə ki, indi biz bir mövqedə olduğu etdiyiniz
biz ikili axtarış edə bilərsiniz.

71
00:03:10,370 --> 00:03:12,560
>> Belə ki, prosesi təkrar edək
addım-addım və saxlamaq

72
00:03:12,560 --> 00:03:14,830
biz getmək kimi neler track.

73
00:03:14,830 --> 00:03:17,980
Belə ki, ilk, biz hesablamaq nə etmək lazımdır
cari serialın orta.

74
00:03:17,980 --> 00:03:20,620
Bəli, biz ilk biz istəyirik demək lazımdır
bütün dəyər 19 axtarır.

75
00:03:20,620 --> 00:03:22,290
Biz sayı 19 tapmaq üçün çalışırıq.

76
00:03:22,290 --> 00:03:25,380
Bu ilk element
array, kataloq sıfır yerləşir

77
00:03:25,380 --> 00:03:28,880
və bu son element
array indeksi 14 yerləşir.

78
00:03:28,880 --> 00:03:31,430
Və belə ki, biz bu başlanğıc və son zəng edəcəyik.

79
00:03:31,430 --> 00:03:35,387
>> Belə ki, biz orta hesablamaq
0 plus 2 bölünür 14 əlavə;

80
00:03:35,387 --> 00:03:36,720
olduqca sadə orta.

81
00:03:36,720 --> 00:03:40,190
Və biz demək olar ki,
orta indi 7.

82
00:03:40,190 --> 00:03:43,370
Belə ki, 15 biz aradığınız nədir?

83
00:03:43,370 --> 00:03:43,940
Xeyr, bu deyil.

84
00:03:43,940 --> 00:03:45,270
Biz 19 arıyorsanız.

85
00:03:45,270 --> 00:03:49,400
Amma biz 19 böyük olduğunu bilirik
ortada aşkar nə çox.

86
00:03:49,400 --> 00:03:52,470
>> Belə ki, biz nə edə nə
başlanğıc nöqtəsi dəyişdirmək

87
00:03:52,470 --> 00:03:57,280
yalnız sağ olmaq
orta və yenidən prosesi təkrar edin.

88
00:03:57,280 --> 00:04:01,690
Biz bunu zaman, biz indi demək
yeni başlanğıc nöqtəsi array yer 8.

89
00:04:01,690 --> 00:04:07,220
Biz səmərəli etdik deyil
15 sol göz ardı hər şey.

90
00:04:07,220 --> 00:04:09,570
Biz yarım aradan sonra
problemin, indi,

91
00:04:09,570 --> 00:04:13,510
əvəzinə axtarış üçün olan
bizim array 15 elementləri,

92
00:04:13,510 --> 00:04:15,610
biz yalnız 7-dən çox axtarmaq lazımdır.

93
00:04:15,610 --> 00:04:17,706
Belə ki, 8 yeni başlanğıc nöqtəsidir.

94
00:04:17,706 --> 00:04:19,600
14 hələ son nöqtəsidir.

95
00:04:19,600 --> 00:04:21,430
>> İndi, biz yenidən bu artıq getmək.

96
00:04:21,430 --> 00:04:22,810
Biz yeni orta hesablamaq.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 2 11 bölünür, 22.

98
00:04:27,130 --> 00:04:28,660
Bu biz aradığınız nədir?

99
00:04:28,660 --> 00:04:30,110
Xeyr, bu deyil.

100
00:04:30,110 --> 00:04:32,930
Biz bir dəyər aradığınız
biz yalnız aşkar nə az.

101
00:04:32,930 --> 00:04:34,721
Beləliklə, biz demək olacaq
yenidən prosesi.

102
00:04:34,721 --> 00:04:38,280
Biz son nöqtəsi dəyişiklik olacaq
yalnız orta sol olsun.

103
00:04:38,280 --> 00:04:41,800
Belə ki, yeni son nöqtəsi 10 olur.

104
00:04:41,800 --> 00:04:44,780
İndi ki, yalnız bir hissəsi
array biz vasitəsilə düzmək lazımdır.

105
00:04:44,780 --> 00:04:48,460
Beləliklə, biz indi aradan qaldırdıq
15 elementləri 12.

106
00:04:48,460 --> 00:04:51,550
Biz bilirik ki, əgər 19
array var, onu

107
00:04:51,550 --> 00:04:57,210
element arasında bir mövcud olmalıdır
8 nömrəli və element sayı 10.

108
00:04:57,210 --> 00:04:59,400
>> Beləliklə, biz daha yeni orta hesablamaq.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 2 9 bölünür, 18.

110
00:05:02,900 --> 00:05:05,074
Və bu halda, baxmaq
hədəf ortasında edir.

111
00:05:05,074 --> 00:05:06,740
Biz aradığınız dəqiq nə tapılmadı.

112
00:05:06,740 --> 00:05:07,780
Biz dayandıra bilər.

113
00:05:07,780 --> 00:05:10,561
Biz uğurla başa
bir ikili axtarış.

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

115
00:05:11,060 --> 00:05:13,930
Beləliklə, biz bu alqoritm bilmək
hədəf çalışır

116
00:05:13,930 --> 00:05:16,070
haradasa serialın içərisində.

117
00:05:16,070 --> 00:05:19,060
Bu alqoritm iş əgər mu
hədəf sıra deyil?

118
00:05:19,060 --> 00:05:20,810
Yaxşı, bu başlamaq edək
yenidən, və bu zaman,

119
00:05:20,810 --> 00:05:23,380
nin element üçün baxaq
Vizual Göründüyü 16,

120
00:05:23,380 --> 00:05:25,620
array hər hansı mövcud deyil.

121
00:05:25,620 --> 00:05:27,110
>> başlanğıc nöqtəsi yenə 0.

122
00:05:27,110 --> 00:05:28,590
son nöqtəsi yenə 14.

123
00:05:28,590 --> 00:05:32,490
O ilk göstəriciləri və
tam array son elementləri.

124
00:05:32,490 --> 00:05:36,057
Və biz prosesi biz yalnız keçmək lazımdır
yolu ilə getdi yenə 16 tapmaq üçün çalışırıq,

125
00:05:36,057 --> 00:05:39,140
hətta vizual baxmayaraq, biz artıq edə bilərsiniz
orada olmaq niyyətində deyil ki, demək.

126
00:05:39,140 --> 00:05:43,450
Biz yalnız əmin, bu alqoritm etmək istəyirəm
, əslində, hələ də bir şəkildə işləyəcək

127
00:05:43,450 --> 00:05:46,310
və yalnız bizi tərk deyil
sonsuz loop yapışdırılmalıdır.

128
00:05:46,310 --> 00:05:48,190
>> Belə ki, addım ilk nə var?

129
00:05:48,190 --> 00:05:50,230
Orta hesablayın
cari serialın.

130
00:05:50,230 --> 00:05:52,790
Orta nədir
cari serialın?

131
00:05:52,790 --> 00:05:54,410
Bəli, bu doğru, 7 var?

132
00:05:54,410 --> 00:05:57,560
2 bölünür 14 plus 0 7.

133
00:05:57,560 --> 00:05:59,280
Biz aradığınız nə 15?

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

135
00:05:59,780 --> 00:06:02,930
Bu olduqca yaxın, lakin biz aradığınız
ki, bir az daha böyük bir dəyər.

136
00:06:02,930 --> 00:06:06,310
>> Beləliklə, biz bu olacaq bilirik ki,
15 solunda heç ola bilər.

137
00:06:06,310 --> 00:06:08,540
hədəf daha böyükdür
nə orta var.

138
00:06:08,540 --> 00:06:12,450
Və belə ki, biz yeni başlanğıc nöqtəsi müəyyən
yalnız orta sağ olsun.

139
00:06:12,450 --> 00:06:16,130
orta, belə ki, hazırda 7
yeni başlanğıc nöqtəsi 8 deyək.

140
00:06:16,130 --> 00:06:18,130
Və biz səmərəli nə var
yenidən həyata göz ardı

141
00:06:18,130 --> 00:06:21,150
serialın bütün sol yarısı.

142
00:06:21,150 --> 00:06:23,750
>> İndi biz təkrar
bir dəfə daha emal.

143
00:06:23,750 --> 00:06:24,910
Yeni orta hesablayın.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 2 11 bölünür, 22.

145
00:06:29,350 --> 00:06:31,060
Biz aradığınız nə 23?

146
00:06:31,060 --> 00:06:31,870
Təəssüf ki, yox.

147
00:06:31,870 --> 00:06:34,930
Biz bir dəyər aradığınız
ki, az 23.

148
00:06:34,930 --> 00:06:37,850
Və bu halda, biz gedirik
son nöqtəsi dəyişdirmək üçün yalnız olmaq

149
00:06:37,850 --> 00:06:40,035
cari orta sol.

150
00:06:40,035 --> 00:06:43,440
cari orta 11 və
belə ki, biz yeni end nöqtəsini qurmaq lazımdır

151
00:06:43,440 --> 00:06:46,980
biz getmək növbəti dəfə
10 bu prosesi.

152
00:06:46,980 --> 00:06:48,660
>> Yenə biz yenə prosesi vasitəsilə getmək.

153
00:06:48,660 --> 00:06:49,640
Orta hesablayın.

154
00:06:49,640 --> 00:06:53,100
2 bölünür 8 plus 10 9.

155
00:06:53,100 --> 00:06:54,750
Biz aradığınız nə 19?

156
00:06:54,750 --> 00:06:55,500
Təəssüf ki, yox.

157
00:06:55,500 --> 00:06:58,050
Biz hələ aradığınız
az bir sıra.

158
00:06:58,050 --> 00:07:02,060
Beləliklə, biz son nöqtəsi bu dəfə dəyişdirmək lazımdır
yalnız orta sol olmalıdır.

159
00:07:02,060 --> 00:07:05,532
orta hazırda 9
belə son nöqtəsi 8 olacaq.

160
00:07:05,532 --> 00:07:07,920
İndi biz yalnız aradığınız
bir element array.

161
00:07:07,920 --> 00:07:10,250
>> Bu serialın orta nədir?

162
00:07:10,250 --> 00:07:13,459
Bəli, bu, 8 başlayır
8 bitir orta 8.

163
00:07:13,459 --> 00:07:14,750
Ki, biz aradığınız nədir?

164
00:07:14,750 --> 00:07:16,339
Biz 17 axtarırsınız?

165
00:07:16,339 --> 00:07:17,380
Xeyr, biz 16 aradığınız.

166
00:07:17,380 --> 00:07:20,160
Bu array var Belə ki,
Bu yerdə mövcud olmalıdır

167
00:07:20,160 --> 00:07:21,935
Hal-hazırda harada sol.

168
00:07:21,935 --> 00:07:23,060
Belə ki, nə biz nə edəcəyik?

169
00:07:23,060 --> 00:07:26,610
Bəli, biz yalnız olmaq üçün son nöqtəsini qurmaq lazımdır
cari orta sol.

170
00:07:26,610 --> 00:07:29,055
Beləliklə, biz 7 son nöqtəsi dəyişdirmək lazımdır.

171
00:07:29,055 --> 00:07:32,120
Siz yalnız nə görürsünüz
baxmayaraq ki, burada oldu?

172
00:07:32,120 --> 00:07:33,370
İndi burada baxın.

173
00:07:33,370 --> 00:07:35,970
>> Start indi sonunda daha böyükdür.

174
00:07:35,970 --> 00:07:39,620
Səmərəli, iki bitir
bizim serialın keçib,

175
00:07:39,620 --> 00:07:42,252
və başlanğıc nöqtəsidir
İndi son nöqtədən sonra.

176
00:07:42,252 --> 00:07:43,960
Yaxşı ki, deyil
sağ, bir mənada?

177
00:07:43,960 --> 00:07:47,960
Belə ki, indi biz nə deyə bilərsiniz biz
ölçüsü 0 alt sıra var.

178
00:07:47,960 --> 00:07:50,110
Və bir dəfə biz kazanılmış edirik
Bu baxımdan, biz indi bilərsiniz

179
00:07:50,110 --> 00:07:53,940
ki, element zəmanət 16
sıra mövcud deyil,

180
00:07:53,940 --> 00:07:56,280
başlanğıc nöqtəsi çünki
və son nöqtə keçib.

181
00:07:56,280 --> 00:07:58,340
Və belə ki, yoxdur.

182
00:07:58,340 --> 00:08:01,340
İndi bu qədər olduğunu qeyd
başlanğıc nöqtəsi və sonunda fərqli

183
00:08:01,340 --> 00:08:02,900
eyni olan qeyd.

184
00:08:02,900 --> 00:08:05,030
Biz axtarır olsaydı,
17 üçün, bu olardı

185
00:08:05,030 --> 00:08:08,870
array, və başlanğıc nöqtəsi olmuşdur
ki, ötən iteration və son nöqtəsi

186
00:08:08,870 --> 00:08:11,820
o xal keçərək əvvəl,
biz 17 tapardılar.

187
00:08:11,820 --> 00:08:15,510
Onlar biz ki keçmək zaman yalnız var
element deyil ki, zəmanət

188
00:08:15,510 --> 00:08:17,180
sıra mövcuddur.

189
00:08:17,180 --> 00:08:20,260
>> Belə ki, bir çox daha az götürək
xətti axtarış daha addımlar.

190
00:08:20,260 --> 00:08:23,250
Ən pis halda, biz idi
n elementlərin siyahısı split

191
00:08:23,250 --> 00:08:27,770
dəfələrlə yarısında hədəf tapmaq üçün
ya çünki hədəf element

192
00:08:27,770 --> 00:08:33,110
son bir yerdə olacaq
bölmə, və ya bütün mövcud deyil.

193
00:08:33,110 --> 00:08:37,830
Ən pis halda belə, biz var
bilirsiniz array parçalamaq?

194
00:08:37,830 --> 00:08:40,510
N dəfə log; biz
problem kəsmək lazımdır

195
00:08:40,510 --> 00:08:42,610
dəfə yarım müəyyən sayda.

196
00:08:42,610 --> 00:08:45,160
Dəfə ki sayı log n.

197
00:08:45,160 --> 00:08:46,510
>> Ən yaxşı ssenari nədir?

198
00:08:46,510 --> 00:08:48,899
Bəli, ilk dəfə
orta hesablamaq,

199
00:08:48,899 --> 00:08:50,190
biz aradığınız nə tapa bilərsiniz.

200
00:08:50,190 --> 00:08:52,150
Bütün əvvəlki
ikili axtarış nümunələri

201
00:08:52,150 --> 00:08:55,489
biz əgər biz yalnız üzərində getdi sonra
element 15 axtarır,

202
00:08:55,489 --> 00:08:57,030
ki, dərhal aşkar olardı.

203
00:08:57,030 --> 00:08:58,321
Bu, çox əvvəlində idi.

204
00:08:58,321 --> 00:09:01,200
Ki, orta idi
bir split ilk cəhdi

205
00:09:01,200 --> 00:09:03,950
ikili axtarış bölgüsü.

206
00:09:03,950 --> 00:09:06,350
>> Və belə pis
halda, ikili axtarış çalışır

207
00:09:06,350 --> 00:09:11,580
əhəmiyyətli dərəcədə daha yaxşı log n, da
ən pis halda xətti axtarış daha.

208
00:09:11,580 --> 00:09:16,210
Ən yaxşı halda, ikili
Axtarış 1 omega çalışır.

209
00:09:16,210 --> 00:09:18,990
Belə ki, ikili axtarış bir çox
xətti axtarış daha yaxşı,

210
00:09:18,990 --> 00:09:23,270
ancaq prosesi ilə məşğul
Siz əvvəl ilk sıra çeşidlənməsi

211
00:09:23,270 --> 00:09:26,140
ikili axtarış enerji leverage.

212
00:09:26,140 --> 00:09:27,130
>> Mən Doug Lloyd edirəm.

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

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