>> [MUSIC PLAYING]
>> DOUG LLOYD: B眉t眉n h眉ququ.
Bel蓹 ki, ikili axtar谋艧 bir deyil biz istifad蓹 ed蓹 bil蓹rsiniz alqoritm
bir s谋ra daxili bir element tapa bil蓹rsiniz.
X蓹tti axtar谋艧 f蓹rqli olaraq, t蓹l蓹b x眉susi 艧蓹rt 蓹vv蓹lc蓹d蓹n g枚r眉艧眉b
lakin bu 莽ox daha 莽ox s蓹m蓹r蓹li 蓹g蓹r var 艧蓹rtdir ki, 蓹slind蓹, bir araya g蓹ldi.
>> Bel蓹 ki, fikir burada n蓹 var?
Bu b枚lm蓹k v蓹 f蓹th edir.
Biz 枚l莽眉s眉n眉 azaltmaq ist蓹yir蓹m yar谋m h蓹r vaxt Axtar谋艧 sah蓹si
bir h蓹d蓹f say谋 tapmaq 眉莽眉n.
Bu harada v蓹ziyy蓹ti baxmayaraq ki, d枚vr蓹y蓹 girir.
Biz yaln谋z g眉c leverage elementl蓹ri aradan qald谋r谋lmas谋 yar谋m
h蓹tta baxmadan Onlara array 莽e艧idl蓹nir 蓹g蓹r.
>> Tam bir mix var varsa, biz yaln谋z 蓹l h蓹yata bilm蓹z
脟眉nki elementl蓹rin yar谋m imtina biz discarding n蓹 bilmir蓹m.
Amma array s谋ralan谋r 蓹g蓹r biz bunu ed蓹 bil蓹rsiniz, 莽眉nki biz
ki, h蓹r 艧eyi bilm蓹k Hal-haz谋rda burada sol
daha a艧a臒谋 olmal谋d谋r d蓹y蓹ri Hal-haz谋rda ist蓹yirik.
V蓹 h蓹r 艧ey 眉莽眉n Biz harada h眉ququ
d蓹y蓹ri daha b枚y眉k olmal谋d谋r Hal-haz谋rda bax谋r谋q.
>> Bel蓹 ki, pseudocode n蓹 Binar axtar谋艧 眉莽眉n add谋mlar?
Biz q蓹d蓹r bu prosesi t蓹krar array v蓹 ya, biz vasit蓹sil蓹 davam kimi,
sub Diziler, ki莽ik 蓹d蓹d orijinal array 枚l莽眉s眉 0 var.
Orta hesablay谋n Cari sub serial谋n.
>> Arad谋臒谋n谋z d蓹y蓹ri 蓹g蓹r array ki element, dayand谋rmaq.
Siz tapd谋.
Bu 蓹lad谋r.
茝ks halda, h蓹d蓹f 蓹g蓹r orta n蓹 az,
bel蓹 d蓹y蓹r 蓹g蓹r biz arad谋臒谋n谋z , biz g枚rm蓹k n蓹 a艧a臒谋
yenid蓹n bu prosesi t蓹krar, lakin 蓹v蓹zin蓹, son n枚qt蓹si d蓹yi艧蓹
orijinal olan tam array tam,
yaln谋z sol olmaq harada biz yaln谋z baxd谋.
>> Biz orta 莽ox y眉ks蓹k idi ki, bilirdi v蓹 ya h蓹d蓹f, orta az idi
v蓹 bel蓹 ki, m枚vcud olmal谋d谋r bu 蓹g蓹r , b眉t眉n array var
haradasa orta sol.
V蓹 bel蓹 ki, biz array qurmaq laz谋md谋r yaln谋z sol yer
yeni bitm蓹 n枚qt蓹sin蓹 kimi orta edir.
茝ksin蓹, h蓹d蓹f 蓹g蓹r orta n蓹 daha 莽ox,
biz eyni ed蓹 proses, lakin 蓹v蓹zin蓹 biz
olmaq ba艧lan臒谋c n枚qt蓹si d蓹yi艧dirm蓹k yaln谋z orta sa臒 眉莽眉n
biz yaln谋z hesablan谋r.
V蓹 sonra, biz yen蓹 prosesi ba艧lay谋r.
>> OK, bu g枚r眉nt眉l蓹m蓹k ed蓹k?
Bel蓹 ki, davam v蓹 burada bir 莽ox var, lakin burada 15 elementl蓹r bir s谋ra var.
V蓹 biz takip saxlan谋lmas谋 olacaq daha 莽ox 艧eyl蓹r bu d蓹f蓹.
Bel蓹 ki, x蓹tti axtar谋艧, biz yaln谋z bir h蓹d蓹f haqq谋nda qay臒谋.
Amma bu d蓹f蓹 ist蓹yirik Biz harada qay臒谋
baxmaq ba艧lay谋r, harada biz axtar谋r dayand谋r谋lmas谋 olunur,
v蓹 orta n蓹 cari serial谋n.
Bel蓹 ki, burada biz ikili axtar谋艧 gedin.
Biz olduqca 莽ox yax艧谋 getm蓹k, sa臒 ist蓹yirik?
M蓹n yaln谋z yazmaq 眉莽眉n gedir蓹m indeksl蓹ri bir s谋ra a艧a臒谋da v蓹 burada.
Bu 蓹sas蓹n yaln谋z n蓹 elementidir serial谋n b蓹hs edirik.
X蓹tti axtar谋艧, biz biz kimi 陌sa qay臒谋
ne莽蓹 bilm蓹k laz谋md谋r biz art谋q iterating edirik elementl蓹ri,
lakin biz, h蓹qiq蓹t蓹n, qay臒谋 yoxdur n蓹 element Hal-haz谋rda bax谋r谋q.
Ikili axtar谋艧, edirik.
V蓹 bel蓹 ki, o, yaln谋z var bir az b蓹l蓹d莽i kimi.
>> Bel蓹likl蓹, biz sa臒, ba艧laya bil蓹rsiniz?
B蓹li, tamamil蓹.
Dedim n蓹 saxla ikili axtar谋艧 haqq谋nda?
Biz bunu ed蓹 bilm蓹z ba艧qa 莽e艧idl蓹nm蓹mi艧 array v蓹 ya,
ki, t蓹min deyil M眉蓹yy蓹n elementl蓹ri v蓹 ya d蓹y蓹rl蓹r deyil
t蓹sad眉f蓹n olan at谋l谋r zaman biz yaln谋z
serial谋n yar谋s谋 ignore q蓹rar.
>> Bel蓹 ki, ikili axtar谋艧 il蓹 bir add谋m Bir s谋ralan谋r array olmal谋d谋r edir.
V蓹 莽e艧idl蓹nm蓹si h蓹r hans谋 bir istifad蓹 ed蓹 bil蓹rsiniz Biz haqq谋nda s枚hb蓹t etdik alqoritml蓹r
ki, m枚vqe almaq 眉莽眉n.
Bel蓹 ki, indi biz bir m枚vqed蓹 oldu臒u etdiyiniz biz ikili axtar谋艧 ed蓹 bil蓹rsiniz.
>> Bel蓹 ki, prosesi t蓹krar ed蓹k add谋m-add谋m v蓹 saxlamaq
biz getm蓹k kimi neler track.
Bel蓹 ki, ilk, biz hesablamaq n蓹 etm蓹k laz谋md谋r cari serial谋n orta.
B蓹li, biz ilk biz ist蓹yirik dem蓹k laz谋md谋r b眉t眉n d蓹y蓹r 19 axtar谋r.
Biz say谋 19 tapmaq 眉莽眉n 莽al谋艧谋r谋q.
Bu ilk element array, kataloq s谋f谋r yerl蓹艧ir
v蓹 bu son element array indeksi 14 yerl蓹艧ir.
V蓹 bel蓹 ki, biz bu ba艧lan臒谋c v蓹 son z蓹ng ed蓹c蓹yik.
>> Bel蓹 ki, biz orta hesablamaq 0 plus 2 b枚l眉n眉r 14 蓹lav蓹;
olduqca sad蓹 orta.
V蓹 biz dem蓹k olar ki, orta indi 7.
Bel蓹 ki, 15 biz arad谋臒谋n谋z n蓹dir?
Xeyr, bu deyil.
Biz 19 ar谋yorsan谋z.
Amma biz 19 b枚y眉k oldu臒unu bilirik ortada a艧kar n蓹 莽ox.
>> Bel蓹 ki, biz n蓹 ed蓹 n蓹 ba艧lan臒谋c n枚qt蓹si d蓹yi艧dirm蓹k
yaln谋z sa臒 olmaq orta v蓹 yenid蓹n prosesi t蓹krar edin.
Biz bunu zaman, biz indi dem蓹k yeni ba艧lan臒谋c n枚qt蓹si array yer 8.
Biz s蓹m蓹r蓹li etdik deyil 15 sol g枚z ard谋 h蓹r 艧ey.
Biz yar谋m aradan sonra problemin, indi,
蓹v蓹zin蓹 axtar谋艧 眉莽眉n olan bizim array 15 elementl蓹ri,
biz yaln谋z 7-d蓹n 莽ox axtarmaq laz谋md谋r.
Bel蓹 ki, 8 yeni ba艧lan臒谋c n枚qt蓹sidir.
14 h蓹l蓹 son n枚qt蓹sidir.
>> 陌ndi, biz yenid蓹n bu art谋q getm蓹k.
Biz yeni orta hesablamaq.
8 plus 14 2 11 b枚l眉n眉r, 22.
Bu biz arad谋臒谋n谋z n蓹dir?
Xeyr, bu deyil.
Biz bir d蓹y蓹r arad谋臒谋n谋z biz yaln谋z a艧kar n蓹 az.
Bel蓹likl蓹, biz dem蓹k olacaq yenid蓹n prosesi.
Biz son n枚qt蓹si d蓹yi艧iklik olacaq yaln谋z orta sol olsun.
Bel蓹 ki, yeni son n枚qt蓹si 10 olur.
陌ndi ki, yaln谋z bir hiss蓹si array biz vasit蓹sil蓹 d眉zm蓹k laz谋md谋r.
Bel蓹likl蓹, biz indi aradan qald谋rd谋q 15 elementl蓹ri 12.
Biz bilirik ki, 蓹g蓹r 19 array var, onu
element aras谋nda bir m枚vcud olmal谋d谋r 8 n枚mr蓹li v蓹 element say谋 10.
>> Bel蓹likl蓹, biz daha yeni orta hesablamaq.
8 plus 10 2 9 b枚l眉n眉r, 18.
V蓹 bu halda, baxmaq h蓹d蓹f ortas谋nda edir.
Biz arad谋臒谋n谋z d蓹qiq n蓹 tap谋lmad谋.
Biz dayand谋ra bil蓹r.
Biz u臒urla ba艧a bir ikili axtar谋艧.
Oldu.
Bel蓹likl蓹, biz bu alqoritm bilm蓹k h蓹d蓹f 莽al谋艧谋r
haradasa serial谋n i莽蓹risind蓹.
Bu alqoritm i艧 蓹g蓹r mu h蓹d蓹f s谋ra deyil?
Yax艧谋, bu ba艧lamaq ed蓹k yenid蓹n, v蓹 bu zaman,
nin element 眉莽眉n baxaq Vizual G枚r眉nd眉y眉 16,
array h蓹r hans谋 m枚vcud deyil.
>> ba艧lan臒谋c n枚qt蓹si yen蓹 0.
son n枚qt蓹si yen蓹 14.
O ilk g枚st蓹ricil蓹ri v蓹 tam array son elementl蓹ri.
V蓹 biz prosesi biz yaln谋z ke莽m蓹k laz谋md谋r yolu il蓹 getdi yen蓹 16 tapmaq 眉莽眉n 莽al谋艧谋r谋q,
h蓹tta vizual baxmayaraq, biz art谋q ed蓹 bil蓹rsiniz orada olmaq niyy蓹tind蓹 deyil ki, dem蓹k.
Biz yaln谋z 蓹min, bu alqoritm etm蓹k ist蓹yir蓹m , 蓹slind蓹, h蓹l蓹 d蓹 bir 艧蓹kild蓹 i艧l蓹y蓹c蓹k
v蓹 yaln谋z bizi t蓹rk deyil sonsuz loop yap谋艧d谋r谋lmal谋d谋r.
>> Bel蓹 ki, add谋m ilk n蓹 var?
Orta hesablay谋n cari serial谋n.
Orta n蓹dir cari serial谋n?
B蓹li, bu do臒ru, 7 var?
2 b枚l眉n眉r 14 plus 0 7.
Biz arad谋臒谋n谋z n蓹 15?
Yox.
Bu olduqca yax谋n, lakin biz arad谋臒谋n谋z ki, bir az daha b枚y眉k bir d蓹y蓹r.
>> Bel蓹likl蓹, biz bu olacaq bilirik ki, 15 solunda he莽 ola bil蓹r.
h蓹d蓹f daha b枚y眉kd眉r n蓹 orta var.
V蓹 bel蓹 ki, biz yeni ba艧lan臒谋c n枚qt蓹si m眉蓹yy蓹n yaln谋z orta sa臒 olsun.
orta, bel蓹 ki, haz谋rda 7 yeni ba艧lan臒谋c n枚qt蓹si 8 dey蓹k.
V蓹 biz s蓹m蓹r蓹li n蓹 var yenid蓹n h蓹yata g枚z ard谋
serial谋n b眉t眉n sol yar谋s谋.
>> 陌ndi biz t蓹krar bir d蓹f蓹 daha emal.
Yeni orta hesablay谋n.
8 plus 14 2 11 b枚l眉n眉r, 22.
Biz arad谋臒谋n谋z n蓹 23?
T蓹蓹ss眉f ki, yox.
Biz bir d蓹y蓹r arad谋臒谋n谋z ki, az 23.
V蓹 bu halda, biz gedirik son n枚qt蓹si d蓹yi艧dirm蓹k 眉莽眉n yaln谋z olmaq
cari orta sol.
cari orta 11 v蓹 bel蓹 ki, biz yeni end n枚qt蓹sini qurmaq laz谋md谋r
biz getm蓹k n枚vb蓹ti d蓹f蓹 10 bu prosesi.
>> Yen蓹 biz yen蓹 prosesi vasit蓹sil蓹 getm蓹k.
Orta hesablay谋n.
2 b枚l眉n眉r 8 plus 10 9.
Biz arad谋臒谋n谋z n蓹 19?
T蓹蓹ss眉f ki, yox.
Biz h蓹l蓹 arad谋臒谋n谋z az bir s谋ra.
Bel蓹likl蓹, biz son n枚qt蓹si bu d蓹f蓹 d蓹yi艧dirm蓹k laz谋md谋r yaln谋z orta sol olmal谋d谋r.
orta haz谋rda 9 bel蓹 son n枚qt蓹si 8 olacaq.
陌ndi biz yaln谋z arad谋臒谋n谋z bir element array.
>> Bu serial谋n orta n蓹dir?
B蓹li, bu, 8 ba艧lay谋r 8 bitir orta 8.
Ki, biz arad谋臒谋n谋z n蓹dir?
Biz 17 axtar谋rs谋n谋z?
Xeyr, biz 16 arad谋臒谋n谋z.
Bu array var Bel蓹 ki, Bu yerd蓹 m枚vcud olmal谋d谋r
Hal-haz谋rda harada sol.
Bel蓹 ki, n蓹 biz n蓹 ed蓹c蓹yik?
B蓹li, biz yaln谋z olmaq 眉莽眉n son n枚qt蓹sini qurmaq laz谋md谋r cari orta sol.
Bel蓹likl蓹, biz 7 son n枚qt蓹si d蓹yi艧dirm蓹k laz谋md谋r.
Siz yaln谋z n蓹 g枚r眉rs眉n眉z baxmayaraq ki, burada oldu?
陌ndi burada bax谋n.
>> Start indi sonunda daha b枚y眉kd眉r.
S蓹m蓹r蓹li, iki bitir bizim serial谋n ke莽ib,
v蓹 ba艧lan臒谋c n枚qt蓹sidir 陌ndi son n枚qt蓹d蓹n sonra.
Yax艧谋 ki, deyil sa臒, bir m蓹nada?
Bel蓹 ki, indi biz n蓹 dey蓹 bil蓹rsiniz biz 枚l莽眉s眉 0 alt s谋ra var.
V蓹 bir d蓹f蓹 biz kazan谋lm谋艧 edirik Bu bax谋mdan, biz indi bil蓹rsiniz
ki, element z蓹man蓹t 16 s谋ra m枚vcud deyil,
ba艧lan臒谋c n枚qt蓹si 莽眉nki v蓹 son n枚qt蓹 ke莽ib.
V蓹 bel蓹 ki, yoxdur.
陌ndi bu q蓹d蓹r oldu臒unu qeyd ba艧lan臒谋c n枚qt蓹si v蓹 sonunda f蓹rqli
eyni olan qeyd.
Biz axtar谋r olsayd谋, 17 眉莽眉n, bu olard谋
array, v蓹 ba艧lan臒谋c n枚qt蓹si olmu艧dur ki, 枚t蓹n iteration v蓹 son n枚qt蓹si
o xal ke莽蓹r蓹k 蓹vv蓹l, biz 17 tapard谋lar.
Onlar biz ki ke莽m蓹k zaman yaln谋z var element deyil ki, z蓹man蓹t
s谋ra m枚vcuddur.
>> Bel蓹 ki, bir 莽ox daha az g枚t眉r蓹k x蓹tti axtar谋艧 daha add谋mlar.
茝n pis halda, biz idi n elementl蓹rin siyah谋s谋 split
d蓹f蓹l蓹rl蓹 yar谋s谋nda h蓹d蓹f tapmaq 眉莽眉n ya 莽眉nki h蓹d蓹f element
son bir yerd蓹 olacaq b枚lm蓹, v蓹 ya b眉t眉n m枚vcud deyil.
茝n pis halda bel蓹, biz var bilirsiniz array par莽alamaq?
N d蓹f蓹 log; biz problem k蓹sm蓹k laz谋md谋r
d蓹f蓹 yar谋m m眉蓹yy蓹n sayda.
D蓹f蓹 ki say谋 log n.
>> 茝n yax艧谋 ssenari n蓹dir?
B蓹li, ilk d蓹f蓹 orta hesablamaq,
biz arad谋臒谋n谋z n蓹 tapa bil蓹rsiniz.
B眉t眉n 蓹vv蓹lki ikili axtar谋艧 n眉mun蓹l蓹ri
biz 蓹g蓹r biz yaln谋z 眉z蓹rind蓹 getdi sonra element 15 axtar谋r,
ki, d蓹rhal a艧kar olard谋.
Bu, 莽ox 蓹vv蓹lind蓹 idi.
Ki, orta idi bir split ilk c蓹hdi
ikili axtar谋艧 b枚lg眉s眉.
>> V蓹 bel蓹 pis halda, ikili axtar谋艧 莽al谋艧谋r
蓹h蓹miyy蓹tli d蓹r蓹c蓹d蓹 daha yax艧谋 log n, da 蓹n pis halda x蓹tti axtar谋艧 daha.
茝n yax艧谋 halda, ikili Axtar谋艧 1 omega 莽al谋艧谋r.
Bel蓹 ki, ikili axtar谋艧 bir 莽ox x蓹tti axtar谋艧 daha yax艧谋,
ancaq prosesi il蓹 m蓹艧臒ul Siz 蓹vv蓹l ilk s谋ra 莽e艧idl蓹nm蓹si
ikili axtar谋艧 enerji leverage.
>> M蓹n Doug Lloyd edir蓹m.
Bu CS 50.