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

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Lahat ng karapatan.

4
00:00:06,220 --> 00:00:08,140
Kaya binary paghahanap ay isang
algorithm maaari naming gamitin

5
00:00:08,140 --> 00:00:10,530
upang mahanap ang isang elemento sa loob ng isang array.

6
00:00:10,530 --> 00:00:14,710
Hindi tulad ng linear paghahanap, ito ay nangangailangan ng isang
espesyal na kondisyon ay natutugunan muna,

7
00:00:14,710 --> 00:00:19,020
ngunit ito ay kaya magkano ang mas mahusay na kung
na kondisyon ay, sa katunayan, natutugunan.

8
00:00:19,020 --> 00:00:20,470
>> Kaya kung ano ang ideya dito?

9
00:00:20,470 --> 00:00:21,780
ito ay hatiin at lupigin.

10
00:00:21,780 --> 00:00:25,100
Gusto naming bawasan ang laki ng
lugar ng paghahanap sa pamamagitan ng kalahati sa bawat oras

11
00:00:25,100 --> 00:00:27,240
upang makahanap ng isang target number.

12
00:00:27,240 --> 00:00:29,520
Ito ay kung saan kondisyon na
dumating sa play, kahit na.

13
00:00:29,520 --> 00:00:32,740
Maaari lamang kami magamit ang lakas ng
inaalis kalahati ng mga elemento

14
00:00:32,740 --> 00:00:36,070
walang kahit na naghahanap sa
ang mga ito kung ang array ay inayos.

15
00:00:36,070 --> 00:00:39,200
>> Kung ito ay isang kumpletong mix up,
hindi namin maaari lamang sa labas ng kamay

16
00:00:39,200 --> 00:00:42,870
itapon ang kalahati ng mga sangkap na ito, dahil
hindi namin alam kung ano ang aming itapon.

17
00:00:42,870 --> 00:00:45,624
Ngunit kung ang mga array ay inayos,
maaari naming gawin iyon, dahil kami

18
00:00:45,624 --> 00:00:48,040
malaman na ang lahat ng bagay sa
iniwan ng kung saan kami ay kasalukuyang ay

19
00:00:48,040 --> 00:00:50,500
ay dapat na mas mababa kaysa sa
halaga hindi namin kasalukuyang sa.

20
00:00:50,500 --> 00:00:52,300
At ang lahat ng bagay sa
kanan ng kung saan tayo ay

21
00:00:52,300 --> 00:00:55,040
dapat mas malaki kaysa sa halaga
kasalukuyan kaming naghahanap sa.

22
00:00:55,040 --> 00:00:58,710
>> Kaya kung ano ang pseudocode
mga hakbang para sa binary paghahanap?

23
00:00:58,710 --> 00:01:02,310
Ulitin namin ang proseso na ito hanggang sa
array o, bilang namin magpatuloy sa pamamagitan ng,

24
00:01:02,310 --> 00:01:07,740
sub array, mas maliit na piraso ng
ang orihinal na array, ay ng laki 0.

25
00:01:07,740 --> 00:01:10,960
Kalkulahin ang Gitnang
ng kasalukuyang sub array.

26
00:01:10,960 --> 00:01:14,460
>> Kung ang halaga na iyong hinahanap para sa ay
sa sangkap na ng array, itigil.

27
00:01:14,460 --> 00:01:15,030
Nahanap mo ito.

28
00:01:15,030 --> 00:01:16,550
Mabuti iyan.

29
00:01:16,550 --> 00:01:19,610
Kung hindi man, kung ang target ay
mas mababa sa kung ano ang sa gitna,

30
00:01:19,610 --> 00:01:23,430
kaya kung ang halaga na kaming naghahanap
para sa mas mababa kaysa sa kung ano ang nakikita namin,

31
00:01:23,430 --> 00:01:26,780
ulitin muli ang proseso na ito, ngunit
baguhin ang mga punto ng pagtatapos, sa halip

32
00:01:26,780 --> 00:01:29,300
ng pagiging ang orihinal
makumpleto full array,

33
00:01:29,300 --> 00:01:34,110
na lamang sa kaliwa
ng kung saan kami lang tumingin.

34
00:01:34,110 --> 00:01:38,940
>> Alam namin na ang gitna ay masyadong mataas,
o ang target ay mas mababa sa gitna,

35
00:01:38,940 --> 00:01:42,210
at sa gayon ay umiiral, kung ito
umiiral sa lahat sa array,

36
00:01:42,210 --> 00:01:44,660
pang lugar sa kaliwa ng ang midpoint.

37
00:01:44,660 --> 00:01:48,120
At kaya kami ay itakda ang array
lokasyon lamang sa kaliwa

38
00:01:48,120 --> 00:01:51,145
ng kalagitnaang bilang bagong punto ng pagtatapos.

39
00:01:51,145 --> 00:01:53,770
Sa kabaligtaran, kung ang target ay
mas malaki kaysa sa kung ano ang sa gitna,

40
00:01:53,770 --> 00:01:55,750
gagawin namin ang eksaktong parehong
proseso, ngunit sa halip namin

41
00:01:55,750 --> 00:01:59,520
baguhin ang start point na maging
lamang sa kanan ng kalagitnaang

42
00:01:59,520 --> 00:02:00,680
kinakalkula lamang namin.

43
00:02:00,680 --> 00:02:03,220
At pagkatapos, simulan namin ang proseso muli.

44
00:02:03,220 --> 00:02:05,220
>> Ni maisalarawan ito, OK?

45
00:02:05,220 --> 00:02:08,620
Kaya mayroong maraming nagaganap at sa dito,
ngunit narito ang isang hanay ng mga 15 na mga elemento.

46
00:02:08,620 --> 00:02:11,400
At kami ay pagpunta sa pagpapanatili ng track
ng isang pulutong mas bagay-bagay sa oras na ito.

47
00:02:11,400 --> 00:02:13,870
Kaya sa linear paghahanap, kami ay
nag-aalaga lang ang tungkol sa isang target.

48
00:02:13,870 --> 00:02:15,869
Ngunit oras na ito ang gusto naming
pag-aalaga tungkol sa kung saan tayo ay

49
00:02:15,869 --> 00:02:18,480
simula sa hitsura, kung saan
kami ay tigil na naghahanap,

50
00:02:18,480 --> 00:02:21,876
at kung ano ang midpoint
ng kasalukuyang array.

51
00:02:21,876 --> 00:02:23,250
Kaya dito namin pumunta sa binary paghahanap.

52
00:02:23,250 --> 00:02:25,290
Humihingi kami ng medyo marami magandang pumunta, di ba?

53
00:02:25,290 --> 00:02:28,650
Lamang ako pagpunta sa ilagay down
ibaba dito isang set ng mga indeks.

54
00:02:28,650 --> 00:02:32,430
Ito ay kung ano talaga element lamang
ng array pinag-uusapan natin ang tungkol sa.

55
00:02:32,430 --> 00:02:34,500
Sa linear paghahanap, kami ay
pag-aalaga, dahil kami ay

56
00:02:34,500 --> 00:02:36,800
kailangan malaman kung gaano karaming
elemento kami ay iterating sa paglipas ng,

57
00:02:36,800 --> 00:02:40,010
ngunit hindi namin talagang pakialam kung ano ang
element kasalukuyan kaming naghahanap sa.

58
00:02:40,010 --> 00:02:41,014
Sa binary paghahanap, ginagawa namin.

59
00:02:41,014 --> 00:02:42,930
At kaya ang mga ay lamang
doon bilang isang maliit na gabay.

60
00:02:42,930 --> 00:02:44,910
>> Kaya maaari naming simulan, di ba?

61
00:02:44,910 --> 00:02:46,240
Well, hindi lubos.

62
00:02:46,240 --> 00:02:48,160
Tandaan kung ano ang sinabi ko
tungkol sa binary paghahanap?

63
00:02:48,160 --> 00:02:50,955
Hindi namin maaaring gawin ito sa isang
unsorted array o ibang tao,

64
00:02:50,955 --> 00:02:55,820
hindi namin ay guaranteeing na ang
ang ilang mga elemento o mga halaga ay hindi

65
00:02:55,820 --> 00:02:57,650
na aksidenteng
tinapon kapag kami lamang

66
00:02:57,650 --> 00:02:59,920
magpasya na huwag pansinin ang kalahati ng array.

67
00:02:59,920 --> 00:03:02,574
>> Kaya hakbang sa isa sa binary paghahanap
ay kailangan mong magkaroon ng isang pinagsunod-sunod array.

68
00:03:02,574 --> 00:03:05,240
At maaari mong gamitin ang alinman sa mga pag-uuri
algorithm na usapan natin ang tungkol

69
00:03:05,240 --> 00:03:06,700
upang makakuha ka sa posisyon na iyon.

70
00:03:06,700 --> 00:03:10,370
Kaya ngayon, hindi namin sa isang posisyon na kung saan ang
maaari naming gawin ang binary paghahanap.

71
00:03:10,370 --> 00:03:12,560
>> Kaya ipaalam sa ulitin ni ang proseso
hakbang-hakbang at panatilihin

72
00:03:12,560 --> 00:03:14,830
subaybayan ng kung ano ang nangyayari na pumunta kami.

73
00:03:14,830 --> 00:03:17,980
Kaya ang kailangan muna naming gawin ay kalkulahin
Gitnang ng kasalukuyang array.

74
00:03:17,980 --> 00:03:20,620
Well, kami ay sabihin kami, una sa
lahat, naghahanap ng mga halaga 19.

75
00:03:20,620 --> 00:03:22,290
Kami ay sinusubukan upang mahanap ang numero 19.

76
00:03:22,290 --> 00:03:25,380
Ang unang elemento ng mga ito
array ay matatagpuan sa index zero,

77
00:03:25,380 --> 00:03:28,880
at ang huling elemento ng ito
array ay matatagpuan sa index 14.

78
00:03:28,880 --> 00:03:31,430
At kaya kami ay tawagin ang mga pagsisimula at pagtatapos.

79
00:03:31,430 --> 00:03:35,387
>> Kaya namin makalkula ang midpoint ng
pagdagdag ng 0 plus 14 na hinati sa 2;

80
00:03:35,387 --> 00:03:36,720
medyo tapat midpoint.

81
00:03:36,720 --> 00:03:40,190
At maaari naming sabihin na
kalagitnaang ay 7 ngayon.

82
00:03:40,190 --> 00:03:43,370
Kaya ay 15 ano ang aming hinahanap para sa?

83
00:03:43,370 --> 00:03:43,940
Hindi.

84
00:03:43,940 --> 00:03:45,270
Kami ay naghahanap para sa 19.

85
00:03:45,270 --> 00:03:49,400
Ngunit alam namin na 19 ay mas malaki
kaysa sa kung ano ang nakita natin sa gitna.

86
00:03:49,400 --> 00:03:52,470
>> Kaya kung ano ang maaari naming gawin ay
baguhin ang start point

87
00:03:52,470 --> 00:03:57,280
upang maging makatarungan sa kanan ng
Gitnang, at ulitin ang proseso muli.

88
00:03:57,280 --> 00:04:01,690
At kapag ginagawa namin na, naming sabihin na ngayon ang
bagong simula point ay array lokasyon 8.

89
00:04:01,690 --> 00:04:07,220
Ano mabisa naming nagawa ay
binalewala ang lahat ng bagay sa kaliwa ng 15.

90
00:04:07,220 --> 00:04:09,570
Naalis na namin ang kalahati
ng mga problema, at ngayon,

91
00:04:09,570 --> 00:04:13,510
sa halip ng pagkakaroon sa paghahanap
higit sa 15 mga elemento sa aming array,

92
00:04:13,510 --> 00:04:15,610
kami ay may lamang sa paghahanap sa paglipas ng 7.

93
00:04:15,610 --> 00:04:17,706
Kaya 8 ay ang bagong simula point.

94
00:04:17,706 --> 00:04:19,600
14 ay ang end point pa rin.

95
00:04:19,600 --> 00:04:21,430
>> At ngayon, pumunta kami sa paglipas ng ito muli.

96
00:04:21,430 --> 00:04:22,810
Kinakalkula namin ang bagong midpoint.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 ay 22, na hinati sa pamamagitan ng 2 ay 11.

98
00:04:27,130 --> 00:04:28,660
Ay ito kung ano ang aming hinahanap para sa?

99
00:04:28,660 --> 00:04:30,110
Hindi.

100
00:04:30,110 --> 00:04:32,930
Kami ay naghahanap para sa isang halaga na
mas mababa sa kung ano ang aming lamang natagpuan.

101
00:04:32,930 --> 00:04:34,721
Kaya kami ay pagpunta sa ulitin
ang proseso muli.

102
00:04:34,721 --> 00:04:38,280
Kami ay pagpunta upang baguhin ang end point sa
maging lamang sa kaliwa ng kalagitnaang.

103
00:04:38,280 --> 00:04:41,800
Kaya ang bagong end point nagiging 10.

104
00:04:41,800 --> 00:04:44,780
At ngayon, na ang bahagi lamang ng
ang array na mayroon kami upang pagbukud-bukurin sa pamamagitan ng.

105
00:04:44,780 --> 00:04:48,460
Kaya ngayon kami ay inalis
12 ng 15 na mga elemento.

106
00:04:48,460 --> 00:04:51,550
Alam namin na kung 19
umiiral sa array, ito

107
00:04:51,550 --> 00:04:57,210
Dapat na umiiral ang lugar sa pagitan ng sangkap
number 8 at elemento number 10.

108
00:04:57,210 --> 00:04:59,400
>> Kaya namin makalkula ang mga bagong midpoint muli.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 ay 18, na hinati sa pamamagitan ng 2 ay 9.

110
00:05:02,900 --> 00:05:05,074
At sa kasong ito, tumingin, ang
target ay sa gitna.

111
00:05:05,074 --> 00:05:06,740
Nakahanap kami ng eksakto kung ano ang aming hinahanap.

112
00:05:06,740 --> 00:05:07,780
Maaari naming ihinto.

113
00:05:07,780 --> 00:05:10,561
Matagumpay namin nakumpleto
isang binary paghahanap.

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

115
00:05:11,060 --> 00:05:13,930
Upang malaman namin ang algorithm na ito
gumagana kapag ang target ay

116
00:05:13,930 --> 00:05:16,070
isang lugar sa loob ng array.

117
00:05:16,070 --> 00:05:19,060
Ito ba ang algorithm trabaho kung
ang target ay hindi sa array?

118
00:05:19,060 --> 00:05:20,810
Well, simulan natin ito ipaalam
muli, at oras na ito,

119
00:05:20,810 --> 00:05:23,380
Tumingin para sa mga elemento ipaalam
16, na biswal maaari naming makita

120
00:05:23,380 --> 00:05:25,620
Hindi umiiral kahit saan sa array.

121
00:05:25,620 --> 00:05:27,110
>> Ang start point ay muli 0.

122
00:05:27,110 --> 00:05:28,590
Ang end point ay muli 14.

123
00:05:28,590 --> 00:05:32,490
Iyon ang mga indeks ng una at
huling elemento ng kumpletong array.

124
00:05:32,490 --> 00:05:36,057
At kami ay pumunta sa pamamagitan ng proseso namin lamang
nagpunta sa pamamagitan ng muli, sinusubukan upang mahanap ang 16,

125
00:05:36,057 --> 00:05:39,140
kahit na biswal, maaari namin na
sabihin na ito ay hindi pagpunta sa maging doon.

126
00:05:39,140 --> 00:05:43,450
Gusto lang namin upang tiyakin na ito algorithm
ay, sa katunayan, gagana pa rin sa ilang mga paraan

127
00:05:43,450 --> 00:05:46,310
at hindi lamang mag-iwan sa amin
natigil sa isang walang-katapusang loop.

128
00:05:46,310 --> 00:05:48,190
>> Kaya kung ano muna ang hakbang?

129
00:05:48,190 --> 00:05:50,230
Kalkulahin ang Gitnang
ng kasalukuyang array.

130
00:05:50,230 --> 00:05:52,790
Ano ang midpoint
ng kasalukuyang array?

131
00:05:52,790 --> 00:05:54,410
Well, ito ay 7, i-right?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 hinati sa 2 ay 7.

133
00:05:57,560 --> 00:05:59,280
Ay 15 kung ano ang namin ang iyong hinahanap?

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

135
00:05:59,780 --> 00:06:02,930
Ito ay malapit sa katangian, ngunit kami ay naghahanap
para sa halaga ng isang bahagyang mas malaki kaysa sa na.

136
00:06:02,930 --> 00:06:06,310
>> Kaya alam namin na ito ay pagpunta sa
wala kahit saan sa kaliwa ng 15.

137
00:06:06,310 --> 00:06:08,540
Ang target ay mas malaki kaysa sa
kung ano ang sa midpoint.

138
00:06:08,540 --> 00:06:12,450
At kaya itinakda namin ang bagong start point sa
maging makatarungan sa kanan ng gitna.

139
00:06:12,450 --> 00:06:16,130
Midpoint ay kasalukuyang 7, kaya
sabihin natin ang bagong simula point ay 8.

140
00:06:16,130 --> 00:06:18,130
At kung ano na namin ng epektibong
gawin muli ay hindi pinansin

141
00:06:18,130 --> 00:06:21,150
ang buong kaliwang kalahati ng array.

142
00:06:21,150 --> 00:06:23,750
>> Ngayon, kami ulitin ang
iproseso isa pang beses.

143
00:06:23,750 --> 00:06:24,910
Kalkulahin ang mga bagong midpoint.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 ay 22, na hinati sa pamamagitan ng 2 ay 11.

145
00:06:29,350 --> 00:06:31,060
Ay 23 kung ano ang namin ang iyong hinahanap?

146
00:06:31,060 --> 00:06:31,870
Sa kasamaang palad, hindi.

147
00:06:31,870 --> 00:06:34,930
Kami ay naghahanap para sa isang halaga
na mas mababa sa 23.

148
00:06:34,930 --> 00:06:37,850
At kaya sa kasong ito, kami ay pagpunta
upang baguhin ang mga punto ng pagtatapos na lamang

149
00:06:37,850 --> 00:06:40,035
sa kaliwa ng kasalukuyang midpoint.

150
00:06:40,035 --> 00:06:43,440
Ang kasalukuyang midpoint ay 11, at
kaya makikita namin-set ang bagong punto ng pagtatapos

151
00:06:43,440 --> 00:06:46,980
para sa susunod na oras na pumunta kami
sa pamamagitan ng prosesong hanggang 10.

152
00:06:46,980 --> 00:06:48,660
>> Muli, pumunta kami sa pamamagitan ng proseso muli.

153
00:06:48,660 --> 00:06:49,640
Kalkulahin ang midpoint.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 na hinati sa pamamagitan ng 2 ay 9.

155
00:06:53,100 --> 00:06:54,750
Ay 19 kung ano ang namin ang iyong hinahanap?

156
00:06:54,750 --> 00:06:55,500
Sa kasamaang palad, hindi.

157
00:06:55,500 --> 00:06:58,050
Kami ay naghahanap pa rin para sa
isang numero na mas mababa kaysa sa na.

158
00:06:58,050 --> 00:07:02,060
Kaya makikita namin baguhin ang mga punto ng pagtatapos ng oras na ito
na lamang sa kaliwa ng kalagitnaang.

159
00:07:02,060 --> 00:07:05,532
Midpoint ay kasalukuyang 9,
kaya ang end point ay 8.

160
00:07:05,532 --> 00:07:07,920
At ngayon, kami ay naghahanap lamang
sa isang solong array elemento.

161
00:07:07,920 --> 00:07:10,250
>> Ano ang Gitnang ng array na ito?

162
00:07:10,250 --> 00:07:13,459
Well, ito ay nagsisimula sa 8, ito
nagtatapos sa 8, ang Gitnang ay 8.

163
00:07:13,459 --> 00:07:14,750
Ay na kung ano ang aming hinahanap para sa?

164
00:07:14,750 --> 00:07:16,339
Ang kami ay naghahanap para sa 17?

165
00:07:16,339 --> 00:07:17,380
Hindi, kami ay naghahanap para sa 16.

166
00:07:17,380 --> 00:07:20,160
Kaya kung umiiral na ito sa array,
ito ay dapat na umiiral sa isang lugar

167
00:07:20,160 --> 00:07:21,935
sa kaliwa ng kung saan kami ay kasalukuyang ay.

168
00:07:21,935 --> 00:07:23,060
Kaya ano pa ang gagawin natin?

169
00:07:23,060 --> 00:07:26,610
Well, kami ay itakda ang end point na lamang
sa kaliwa ng kasalukuyang midpoint.

170
00:07:26,610 --> 00:07:29,055
Kaya makikita namin baguhin ang end point sa 7.

171
00:07:29,055 --> 00:07:32,120
Nakikita mo ba kung ano lang
nangyari dito, bagaman?

172
00:07:32,120 --> 00:07:33,370
Hanapin dito ngayon.

173
00:07:33,370 --> 00:07:35,970
>> Start ay mas malaki sa dulo ngayon.

174
00:07:35,970 --> 00:07:39,620
Mabisa, ng dalawang dulo
ng aming array na tumawid,

175
00:07:39,620 --> 00:07:42,252
at ang simula punto ay
ngayon pagkatapos ng punto ng pagtatapos.

176
00:07:42,252 --> 00:07:43,960
Well, na hindi
gumawa ng anumang kahulugan, tama?

177
00:07:43,960 --> 00:07:47,960
Kaya ngayon, kung ano ang maaari naming sabihin ay namin
magkaroon ng isang sub hanay ng mga laki 0.

178
00:07:47,960 --> 00:07:50,110
At sa sandaling kami ay tapat na paraan upang
puntong ito, maaari naming ngayon

179
00:07:50,110 --> 00:07:53,940
garantiya na elemento na 16
Hindi umiiral sa array,

180
00:07:53,940 --> 00:07:56,280
dahil ang start point
at end point na tumawid.

181
00:07:56,280 --> 00:07:58,340
At kaya ito ay hindi doon.

182
00:07:58,340 --> 00:08:01,340
Ngayon, mapapansin na ito ay bahagyang
naiiba kaysa sa start point at pagtatapos

183
00:08:01,340 --> 00:08:02,900
point sa pagiging pareho.

184
00:08:02,900 --> 00:08:05,030
Kung kami ay naghahanap
para sa 17, ito ay may

185
00:08:05,030 --> 00:08:08,870
ay sa array, at ang start point
at end point ng na huling pag-ulit

186
00:08:08,870 --> 00:08:11,820
bago tumawid ang mga puntos,
Gusto namin nakita ang 17 doon.

187
00:08:11,820 --> 00:08:15,510
Ito ay lamang kapag sila ay tatawid na aming makakaya
garantiya na ang mga elemento ay hindi

188
00:08:15,510 --> 00:08:17,180
umiiral sa array.

189
00:08:17,180 --> 00:08:20,260
>> Kaya sabihin kumuha ng isang pulutong ng mas kaunting
mga hakbang sa linear paghahanap.

190
00:08:20,260 --> 00:08:23,250
Sa pinakamasama kaso sitwasyon, nagkaroon kami
sa split up ng isang listahan ng mga elemento n

191
00:08:23,250 --> 00:08:27,770
paulit-ulit sa loob ng kalahating upang mahanap ang target,
alinman dahil ang target element

192
00:08:27,770 --> 00:08:33,110
ay isang lugar sa huling
division, o ito ay hindi na umiiral sa lahat.

193
00:08:33,110 --> 00:08:37,830
Kaya sa pinakamasama kaso, kami ay may sa
maghiwalay ang array-- ang kilala mo?

194
00:08:37,830 --> 00:08:40,510
Log ng n beses; tayo
upang kunin ang mga problema

195
00:08:40,510 --> 00:08:42,610
sa kalahati ng isang tiyak na bilang ng beses.

196
00:08:42,610 --> 00:08:45,160
Na bilang ng mga beses ay log n.

197
00:08:45,160 --> 00:08:46,510
>> Ano ang pinakamahusay na kaso sitwasyon?

198
00:08:46,510 --> 00:08:48,899
Well, sa unang pagkakataon namin
kalkulahin ang Gitnang,

199
00:08:48,899 --> 00:08:50,190
nakita namin kung ano ang aming hinahanap.

200
00:08:50,190 --> 00:08:52,150
Sa lahat ng mga nakaraang
mga halimbawa sa binary paghahanap

201
00:08:52,150 --> 00:08:55,489
lang kami ay wala sa loob, kung kami ay
ay naghahanap ng mga element 15,

202
00:08:55,489 --> 00:08:57,030
sana ay natagpuan namin na agad.

203
00:08:57,030 --> 00:08:58,321
Iyon ay sa pinakadulo simula.

204
00:08:58,321 --> 00:09:01,200
Iyon ay ang Gitnang ng
ang unang pagtatangka sa isang split

205
00:09:01,200 --> 00:09:03,950
ng isang dibisyon sa binary paghahanap.

206
00:09:03,950 --> 00:09:06,350
>> At kaya sa pinakamalala
kaso, tumatakbo binary search

207
00:09:06,350 --> 00:09:11,580
in log n, na kung saan ay malaki mas mahusay
kaysa sa haba ng paghahanap, sa pinakamasama kaso.

208
00:09:11,580 --> 00:09:16,210
Sa pinakamahusay na kaso, binary
search tumatakbo sa wakas ng 1.

209
00:09:16,210 --> 00:09:18,990
Kaya binary paghahanap ay isang pulutong
mas mahusay kaysa sa linear paghahanap,

210
00:09:18,990 --> 00:09:23,270
ngunit ikaw ay may sa pakikitungo sa proseso ng
paghihiwalay muna ang iyong array bago ka makakapag

211
00:09:23,270 --> 00:09:26,140
pagkilos ang kapangyarihan ng binary paghahanap.

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

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

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