[Music kucheza] 

DOUG LLOYD: zote haki. Hivyo search binary ni algorithm tunaweza kutumia kupata kipengele ndani ya safu. Tofauti na tafuta linear, inahitaji hali maalum kuwa alikutana kabla, lakini ni hivyo ufanisi mkubwa zaidi kama kwamba hali ni, kwa kweli, alikutana. 

Kwa hiyo kile ni wazo hapa? ni mgawanyiko na kushinda. Tunataka kupunguza ukubwa wa eneo la na nusu kila wakati ili kupata idadi ya lengo. Hii ni pale ambapo hali hiyo linachukua nafasi, ingawa. Tunaweza kujiinua nguvu ya pekee kuondoa nusu ya mambo bila hata kuangalia yao kama safu ni Iliyopangwa. 

Kama ni kamili mchanganyiko up, hatuwezi tu na mikono kuondokana na nusu ya vipengele, kwa sababu hatujui nini sisi ni kutupa. Lakini kama safu ni yamepangwa, tunaweza kufanya hivyo, kwa sababu sisi tunajua kwamba kila kitu kushoto ya ambapo sisi sasa ni Lazima kuwa chini zaidi kuliko thamani tuko sasa katika. Na kila kitu kwa haki ya ambapo sisi ni lazima kuwa kubwa kuliko thamani sasa tuko kuangalia. 

Basi nini pseudocode hatua kwa kutafuta binary? Sisi kurudia utaratibu huu mpaka safu au, kama sisi kuendelea kupitia, arrays ndogo, vipande vidogo vya awali safu, ni ya kawaida 0. Mahesabu ya midpoint ya sasa ya ndogo safu. 

Kama thamani wewe kutafuta ni kwa kuwa kipengele cha safu, kuacha. Wewe kupatikana. Hiyo ni kubwa. Vinginevyo, kama lengo ni chini ya nini katikati, hivyo kama thamani sisi ni kuangalia kwa ni chini ya kile sisi kuona, kurudia utaratibu huu tena, lakini mabadiliko hatua ya mwisho, badala ya kuwa awali kukamilisha safu kamili, kwa kuwa tu wa kushoto ya ambapo sisi tu inaonekana. 

Sisi alijua kwamba katikati kilikuwa juu sana, au lengo ilikuwa chini ya katikati, na hivyo ni lazima kuwepo, ikiwa ni ipo wakati wote katika safu, mahali fulani kwa upande wa kushoto wa midpoint. Na hivyo tutaweza kuweka safu eneo tu kwa upande wa kushoto ya midpoint kama mpya hatua ya mwisho. Kinyume chake, kama lengo ni kubwa kuliko nini katikati, tunafanya exact mchakato, lakini badala yake sisi mabadiliko kuanza hatua ya kuwa tu na haki ya midpoint sisi tu mahesabu. Na kisha, sisi kuanza mchakato tena. 

Hebu taswira hii, sawa? Hivyo kuna mengi kwenda na juu ya hapa, lakini hapa ni safu ya vipengele 15. Na tunakwenda kuwa kuweka wimbo ya mengi zaidi mambo wakati huu. Hivyo katika kutafuta linear, tulikuwa tu kujali juu ya lengo. Lakini wakati huu tunataka huduma ya juu ambapo ni sisi mapya ya kuangalia, ambapo ni sisi kuacha kuangalia, na nini midpoint wa safu ya sasa. Hivyo hapa sisi kwenda na kutafuta binary. Sisi ni pretty much vizuri kwenda, haki? Mimi tu kwenda kuweka chini chini hapa seti ya fahirisi. Hii ni kimsingi tu kile kipengele wa safu tunazungumzia. Pamoja na tafuta linear, sisi huduma, kwa vile sisi haja ya kujua jinsi wengi mambo tuko iterating juu, lakini sisi si kweli huduma ya kile kipengele tuko sasa kuangalia. Katika kutafuta binary, sisi kufanya. Na hivyo wale ni tu kuna kama mwongozo kidogo. 

Ili tuweze kuanza, sawa? Naam, si kabisa. Kumbuka kile alisema kuhusu tafuta binary? Hatuwezi kufanya hivyo juu ya zisizochambuliwa safu au mwingine, sisi si kuhakikisha kuwa mambo fulani au maadili si kuwa ajali kuondolewa wakati sisi tu kuamua kupuuza nusu ya safu. 

Hivyo hatua moja kwa binary tafuta ni lazima uwe na safu yamepangwa. Na unaweza kutumia yoyote ya kuchagua algorithms tumekuwa aliyesema kuhusu kupata wewe nafasi hiyo. Hivyo sasa, tuko katika nafasi ambapo tunaweza kufanya search binary. 

Basi hebu kurudia utaratibu hatua kwa hatua na kuweka wimbo wa nini kinatokea kama sisi kwenda. Hivyo kwanza tunahitaji kufanya ni mahesabu ya midpoint wa safu ya sasa. Naam, tutaweza kusema tuko, kwanza ya zote, kuangalia kwa thamani 19. Sisi ni kujaribu kupata idadi 19. Sehemu ya kwanza ya hii safu iko katika ripoti sifuri, na kipengele mwisho wa hii safu iko katika ripoti 14. Na hivyo tutaweza kuwaita wale mwanzo na mwisho. 

Hivyo sisi mahesabu ya midpoint na kuongeza 0 pamoja na 14 kugawanywa na 2; pretty moja kwa moja midpoint. Na tunaweza kusema kwamba midpoint ni sasa 7. Hivyo ni 15 nini sisi ni kuangalia kwa? Hakuna, siyo. Sisi ni kuangalia kwa 19. Lakini tunajua kwamba 19 ni mkubwa kuliko yale sisi kupatikana katika katikati. 

Hivyo nini tunaweza kufanya ni mabadiliko kuanza hatua kwa kuwa tu na haki ya midpoint, na kurudia utaratibu tena. Na wakati sisi kufanya hivyo, sisi sasa wanasema mpya kuanza hatua ni safu eneo 8. Nini tumekuwa kufanyika ni ufanisi kupuuzwa kila kitu kwa upande wa kushoto wa 15. Tumekuwa kuondolewa nusu ya tatizo, na sasa, badala ya kuwa na kutafuta zaidi ya 15 vipengele katika safu yetu, sisi tu kuwa na kutafuta juu ya 7. Hivyo 8 ni mpya kuanza hatua. 14 bado ni hatua ya mwisho. 

Na sasa, sisi kwenda juu hii tena. Sisi mahesabu midpoint mpya. 8 pamoja na 14 ni 22, kugawanywa na 2 ni 11. Je, hii ni nini sisi ni kuangalia kwa? Hakuna, siyo. Sisi ni kuangalia kwa thamani hiyo ni chini ya kile sisi tu kupatikana. Hivyo sisi ni kwenda kurudia mchakato tena. Tunakwenda kubadili hatua ya mwisho kwa kuwa tu kwa upande wa kushoto wa midpoint. Kwa hiyo mpya hatua ya mwisho inakuwa 10. Na sasa, hiyo ni sehemu tu ya safu tuna aina kupitia. Hivyo tuna sasa kuondolewa 12 ya vipengele 15. Tunajua kwamba kama 19 lipo katika safu, lazima kuwepo mahali fulani kati ya kipengele idadi 8 na kipengele namba 10. 

Hivyo sisi mahesabu ya midpoint mpya tena. 8 pamoja na 10 ni 18, kugawanywa na 2 ni 9. Na katika kesi hii, angalia, Lengo ni katikati. Tulikuta nini hasa sisi ni kuangalia kwa. Tunaweza kuacha. Sisi mafanikio ya kumaliza tafuta binary. Sawa. Hivyo tunajua algorithm hii kazi kama lengo ni mahali fulani ndani ya safu. Je, hii kazi algorithm kama Lengo siyo katika safu? Naam, hebu kuanza yake tena, na wakati huu, hebu angalia kwa kipengele 16, ambayo kuibua tunaweza kuona haipo popote katika safu. 

Kuanza hatua ni tena 0. Hatua ya mwisho ni tena 14. Hayo ni fahirisi ya kwanza na mambo ya mwisho wa safu kamili. Na tutaweza kwenda kupitia mchakato sisi tu safari kwa kupitia tena, kujaribu kupata 16, ingawa kuibua, tunaweza tayari kuwaambia kwamba si kwenda kuwa huko. Sisi tu wanataka kuhakikisha algorithm hii itakuwa, kwa kweli, bado kazi katika baadhi ya njia na si tu kutuacha kukwama katika kitanzi usio. 

Basi nini hatua ya kwanza? Mahesabu ya midpoint wa safu ya sasa. Nini midpoint wa safu ya sasa? Naam, ni 7, sawa? 14 pamoja na 0 kugawanywa na 2 ni 7. Ni 15 nini sisi ni kuangalia kwa? Hakuna Ni pretty karibu, lakini sisi tunataka kwa thamani kubwa kidogo kuliko hiyo. 

Hivyo tunajua kwamba itakuja kuwa mahali pa kushoto ya 15. Lengo ni mkubwa kuliko nini katika midpoint. Na hivyo sisi kuweka mpya kuanza hatua ya kuwa tu na haki ya katikati. Midpoint sasa 7, hivyo hebu sema mpya kuanza hatua ni 8. Na nini tumekuwa ufanisi amefanya tena ni kupuuzwa nzima kushoto nusu ya safu. 

Sasa, sisi kurudia mchakato mara moja zaidi. Mahesabu ya midpoint mpya. 8 pamoja na 14 ni 22, kugawanywa na 2 ni 11. Ni 23 nini sisi ni kuangalia kwa? Kwa bahati mbaya, hakuna. Sisi ni kuangalia kwa thamani kuwa ni chini ya 23. Na hivyo katika kesi hii, tunakwenda kubadili hatua ya mwisho kwa kuwa tu upande wa kushoto wa midpoint ya sasa. Midpoint sasa ni 11, na hivyo tutaweza kuweka mpya hatua ya mwisho kwa mara ya pili, twende kupitia utaratibu huu hadi 10. 

Tena, sisi kupitia mchakato tena. Mahesabu ya midpoint. 8 pamoja na 10 kugawanywa na 2 ni 9. Ni 19 nini sisi ni kuangalia kwa? Kwa bahati mbaya, hakuna. Sisi ni bado kuangalia kwa idadi kidogo kuliko hivyo. Hivyo tutaweza kubadili hatua ya mwisho wakati huu kwa kuwa tu kwa upande wa kushoto wa midpoint. Midpoint sasa 9, hivyo hatua ya mwisho itakuwa 8. Na sasa, sisi ni kuangalia tu katika moja ya kipengele safu. 

Nini midpoint wa safu hii? Naam, ni kuanza saa 8, ni kuishia katika 8, midpoint ni 8. Ni kwamba kile sisi ni kuangalia kwa? Je, sisi kuangalia kwa 17? Hapana, sisi ni kuangalia kwa ajili ya 16. Hivyo kama ipo katika safu, ni lazima kuwepo mahali fulani upande wa kushoto wa ambapo sisi sasa ni. Kwa hiyo kile ni sisi kwenda kufanya? Vizuri, tutaweza kuweka hatua ya mwisho kwa kuwa tu upande wa kushoto wa midpoint ya sasa. Hivyo tutaweza kubadili hatua ya mwisho kwa 7. Je, unaweza kuona nini tu kilichotokea hapa, ingawa? Angalia hapa sasa. 

Mwanzo ni sasa zaidi kuliko mwisho. Kwa ufanisi, ncha mbili wa safu yetu wamevuka, na kuanza hatua ni sasa baada ya hatua ya mwisho. Naam, hiyo haina maana yoyote, sawa? Hivyo sasa, nini tunaweza kusema sisi ni na safu ndogo ya ukubwa 0. Na mara moja sisi ni wamezipata kwa hatua hii, tunaweza sasa kuhakikisha kwamba kipengele 16 haipo katika safu, kwa sababu kuanza hatua na hatua ya mwisho wamevuka. Na hivyo ni huko. Sasa, taarifa kwamba hii ni kidogo tofauti na kuanza hatua na mwisho uhakika kuwa sawa. Kama tungekuwa kuangalia kwa 17, ingekuwa wamekuwa katika safu, na kuanza hatua na hatua ya mwisho ya kwamba iteration mwisho kabla pointi hizo shilingi, tunataka wamegundua 17 huko. Ni wakati wao kuvuka kwamba tunaweza tu kuhakikisha kwamba kipengele haina zipo katika safu. 

Basi hebu kuchukua mengi wachache hatua ya kutafuta linear. Katika mazingira ya kesi mbaya, tulikuwa na kugawa orodha ya mambo n mara kwa mara katika nusu ili kupata lengo, ama kwa sababu lengo kipengele itakuwa mahali fulani katika mwisho mgawanyiko, au haipo kabisa. Hivyo katika hali mbaya zaidi, tuna wameigawanya array-- gani unajua? Fungua wa nyakati n; sisi na kupunguza tatizo katika idadi fulani ya nyakati nusu. Hiyo idadi ya nyakati ni gogo n. 

Nini bora kesi mazingira? Naam, kwanza wakati sisi mahesabu ya midpoint, tunaona nini sisi ni kuangalia kwa. Katika zote za awali mifano juu ya kutafuta binary tumekuwa tu wamekwenda juu, kama tulikuwa na wamekuwa kutafuta kipengele 15, tunataka wamegundua kwamba mara moja. Hiyo ilikuwa mwanzoni kabisa. Hiyo ilikuwa ni midpoint ya jaribio la kwanza katika mgawanyiko ya mgawanyiko katika kutafuta mapacha. 

Na hivyo katika hali mbaya zaidi kesi, tafuta binary anaendesha katika logi n, ambayo ina unafuu zaidi kuliko tafuta linear, katika hali mbaya zaidi. Katika kesi bora, mapacha search anaendesha katika omega ya 1. Hivyo search binary ni mengi bora kuliko tafuta linear, lakini wewe kuwa na kushughulika na mchakato wa kuchagua safu yako kwanza kabla unaweza kujiinua nguvu ya kutafuta binary. 

Mimi nina Doug Lloyd. Hii ni CS 50.