>> [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.