[MUSIC nagpe-play] 

DOUG LLOYD: Lahat ng karapatan. Kaya binary paghahanap ay isang algorithm maaari naming gamitin upang mahanap ang isang elemento sa loob ng isang array. Hindi tulad ng linear paghahanap, ito ay nangangailangan ng isang espesyal na kondisyon ay natutugunan muna, ngunit ito ay kaya magkano ang mas mahusay na kung na kondisyon ay, sa katunayan, natutugunan. 

Kaya kung ano ang ideya dito? ito ay hatiin at lupigin. Gusto naming bawasan ang laki ng lugar ng paghahanap sa pamamagitan ng kalahati sa bawat oras upang makahanap ng isang target number. Ito ay kung saan kondisyon na dumating sa play, kahit na. Maaari lamang kami magamit ang lakas ng inaalis kalahati ng mga elemento walang kahit na naghahanap sa ang mga ito kung ang array ay inayos. 

Kung ito ay isang kumpletong mix up, hindi namin maaari lamang sa labas ng kamay itapon ang kalahati ng mga sangkap na ito, dahil hindi namin alam kung ano ang aming itapon. Ngunit kung ang mga array ay inayos, maaari naming gawin iyon, dahil kami malaman na ang lahat ng bagay sa iniwan ng kung saan kami ay kasalukuyang ay ay dapat na mas mababa kaysa sa halaga hindi namin kasalukuyang sa. At ang lahat ng bagay sa kanan ng kung saan tayo ay dapat mas malaki kaysa sa halaga kasalukuyan kaming naghahanap sa. 

Kaya kung ano ang pseudocode mga hakbang para sa binary paghahanap? Ulitin namin ang proseso na ito hanggang sa array o, bilang namin magpatuloy sa pamamagitan ng, sub array, mas maliit na piraso ng ang orihinal na array, ay ng laki 0. Kalkulahin ang Gitnang ng kasalukuyang sub array. 

Kung ang halaga na iyong hinahanap para sa ay sa sangkap na ng array, itigil. Nahanap mo ito. Mabuti iyan. Kung hindi man, kung ang target ay mas mababa sa kung ano ang sa gitna, kaya kung ang halaga na kaming naghahanap para sa mas mababa kaysa sa kung ano ang nakikita namin, ulitin muli ang proseso na ito, ngunit baguhin ang mga punto ng pagtatapos, sa halip ng pagiging ang orihinal makumpleto full array, na lamang sa kaliwa ng kung saan kami lang tumingin. 

Alam namin na ang gitna ay masyadong mataas, o ang target ay mas mababa sa gitna, at sa gayon ay umiiral, kung ito umiiral sa lahat sa array, pang lugar sa kaliwa ng ang midpoint. At kaya kami ay itakda ang array lokasyon lamang sa kaliwa ng kalagitnaang bilang bagong punto ng pagtatapos. Sa kabaligtaran, kung ang target ay mas malaki kaysa sa kung ano ang sa gitna, gagawin namin ang eksaktong parehong proseso, ngunit sa halip namin baguhin ang start point na maging lamang sa kanan ng kalagitnaang kinakalkula lamang namin. At pagkatapos, simulan namin ang proseso muli. 

Ni maisalarawan ito, OK? Kaya mayroong maraming nagaganap at sa dito, ngunit narito ang isang hanay ng mga 15 na mga elemento. At kami ay pagpunta sa pagpapanatili ng track ng isang pulutong mas bagay-bagay sa oras na ito. Kaya sa linear paghahanap, kami ay nag-aalaga lang ang tungkol sa isang target. Ngunit oras na ito ang gusto naming pag-aalaga tungkol sa kung saan tayo ay simula sa hitsura, kung saan kami ay tigil na naghahanap, at kung ano ang midpoint ng kasalukuyang array. Kaya dito namin pumunta sa binary paghahanap. Humihingi kami ng medyo marami magandang pumunta, di ba? Lamang ako pagpunta sa ilagay down ibaba dito isang set ng mga indeks. Ito ay kung ano talaga element lamang ng array pinag-uusapan natin ang tungkol sa. Sa linear paghahanap, kami ay pag-aalaga, dahil kami ay kailangan malaman kung gaano karaming elemento kami ay iterating sa paglipas ng, ngunit hindi namin talagang pakialam kung ano ang element kasalukuyan kaming naghahanap sa. Sa binary paghahanap, ginagawa namin. At kaya ang mga ay lamang doon bilang isang maliit na gabay. 

Kaya maaari naming simulan, di ba? Well, hindi lubos. Tandaan kung ano ang sinabi ko tungkol sa binary paghahanap? Hindi namin maaaring gawin ito sa isang unsorted array o ibang tao, hindi namin ay guaranteeing na ang ang ilang mga elemento o mga halaga ay hindi na aksidenteng tinapon kapag kami lamang magpasya na huwag pansinin ang kalahati ng array. 

Kaya hakbang sa isa sa binary paghahanap ay kailangan mong magkaroon ng isang pinagsunod-sunod array. At maaari mong gamitin ang alinman sa mga pag-uuri algorithm na usapan natin ang tungkol upang makakuha ka sa posisyon na iyon. Kaya ngayon, hindi namin sa isang posisyon na kung saan ang maaari naming gawin ang binary paghahanap. 

Kaya ipaalam sa ulitin ni ang proseso hakbang-hakbang at panatilihin subaybayan ng kung ano ang nangyayari na pumunta kami. Kaya ang kailangan muna naming gawin ay kalkulahin Gitnang ng kasalukuyang array. Well, kami ay sabihin kami, una sa lahat, naghahanap ng mga halaga 19. Kami ay sinusubukan upang mahanap ang numero 19. Ang unang elemento ng mga ito array ay matatagpuan sa index zero, at ang huling elemento ng ito array ay matatagpuan sa index 14. At kaya kami ay tawagin ang mga pagsisimula at pagtatapos. 

Kaya namin makalkula ang midpoint ng pagdagdag ng 0 plus 14 na hinati sa 2; medyo tapat midpoint. At maaari naming sabihin na kalagitnaang ay 7 ngayon. Kaya ay 15 ano ang aming hinahanap para sa? Hindi. Kami ay naghahanap para sa 19. Ngunit alam namin na 19 ay mas malaki kaysa sa kung ano ang nakita natin sa gitna. 

Kaya kung ano ang maaari naming gawin ay baguhin ang start point upang maging makatarungan sa kanan ng Gitnang, at ulitin ang proseso muli. At kapag ginagawa namin na, naming sabihin na ngayon ang bagong simula point ay array lokasyon 8. Ano mabisa naming nagawa ay binalewala ang lahat ng bagay sa kaliwa ng 15. Naalis na namin ang kalahati ng mga problema, at ngayon, sa halip ng pagkakaroon sa paghahanap higit sa 15 mga elemento sa aming array, kami ay may lamang sa paghahanap sa paglipas ng 7. Kaya 8 ay ang bagong simula point. 14 ay ang end point pa rin. 

At ngayon, pumunta kami sa paglipas ng ito muli. Kinakalkula namin ang bagong midpoint. 8 plus 14 ay 22, na hinati sa pamamagitan ng 2 ay 11. Ay ito kung ano ang aming hinahanap para sa? Hindi. Kami ay naghahanap para sa isang halaga na mas mababa sa kung ano ang aming lamang natagpuan. Kaya kami ay pagpunta sa ulitin ang proseso muli. Kami ay pagpunta upang baguhin ang end point sa maging lamang sa kaliwa ng kalagitnaang. Kaya ang bagong end point nagiging 10. At ngayon, na ang bahagi lamang ng ang array na mayroon kami upang pagbukud-bukurin sa pamamagitan ng. Kaya ngayon kami ay inalis 12 ng 15 na mga elemento. Alam namin na kung 19 umiiral sa array, ito Dapat na umiiral ang lugar sa pagitan ng sangkap number 8 at elemento number 10. 

Kaya namin makalkula ang mga bagong midpoint muli. 8 plus 10 ay 18, na hinati sa pamamagitan ng 2 ay 9. At sa kasong ito, tumingin, ang target ay sa gitna. Nakahanap kami ng eksakto kung ano ang aming hinahanap. Maaari naming ihinto. Matagumpay namin nakumpleto isang binary paghahanap. Lahat tama. Upang malaman namin ang algorithm na ito gumagana kapag ang target ay isang lugar sa loob ng array. Ito ba ang algorithm trabaho kung ang target ay hindi sa array? Well, simulan natin ito ipaalam muli, at oras na ito, Tumingin para sa mga elemento ipaalam 16, na biswal maaari naming makita Hindi umiiral kahit saan sa array. 

Ang start point ay muli 0. Ang end point ay muli 14. Iyon ang mga indeks ng una at huling elemento ng kumpletong array. At kami ay pumunta sa pamamagitan ng proseso namin lamang nagpunta sa pamamagitan ng muli, sinusubukan upang mahanap ang 16, kahit na biswal, maaari namin na sabihin na ito ay hindi pagpunta sa maging doon. Gusto lang namin upang tiyakin na ito algorithm ay, sa katunayan, gagana pa rin sa ilang mga paraan at hindi lamang mag-iwan sa amin natigil sa isang walang-katapusang loop. 

Kaya kung ano muna ang hakbang? Kalkulahin ang Gitnang ng kasalukuyang array. Ano ang midpoint ng kasalukuyang array? Well, ito ay 7, i-right? 14 plus 0 hinati sa 2 ay 7. Ay 15 kung ano ang namin ang iyong hinahanap? Hindi. Ito ay malapit sa katangian, ngunit kami ay naghahanap para sa halaga ng isang bahagyang mas malaki kaysa sa na. 

Kaya alam namin na ito ay pagpunta sa wala kahit saan sa kaliwa ng 15. Ang target ay mas malaki kaysa sa kung ano ang sa midpoint. At kaya itinakda namin ang bagong start point sa maging makatarungan sa kanan ng gitna. Midpoint ay kasalukuyang 7, kaya sabihin natin ang bagong simula point ay 8. At kung ano na namin ng epektibong gawin muli ay hindi pinansin ang buong kaliwang kalahati ng array. 

Ngayon, kami ulitin ang iproseso isa pang beses. Kalkulahin ang mga bagong midpoint. 8 plus 14 ay 22, na hinati sa pamamagitan ng 2 ay 11. Ay 23 kung ano ang namin ang iyong hinahanap? Sa kasamaang palad, hindi. Kami ay naghahanap para sa isang halaga na mas mababa sa 23. At kaya sa kasong ito, kami ay pagpunta upang baguhin ang mga punto ng pagtatapos na lamang sa kaliwa ng kasalukuyang midpoint. Ang kasalukuyang midpoint ay 11, at kaya makikita namin-set ang bagong punto ng pagtatapos para sa susunod na oras na pumunta kami sa pamamagitan ng prosesong hanggang 10. 

Muli, pumunta kami sa pamamagitan ng proseso muli. Kalkulahin ang midpoint. 8 plus 10 na hinati sa pamamagitan ng 2 ay 9. Ay 19 kung ano ang namin ang iyong hinahanap? Sa kasamaang palad, hindi. Kami ay naghahanap pa rin para sa isang numero na mas mababa kaysa sa na. Kaya makikita namin baguhin ang mga punto ng pagtatapos ng oras na ito na lamang sa kaliwa ng kalagitnaang. Midpoint ay kasalukuyang 9, kaya ang end point ay 8. At ngayon, kami ay naghahanap lamang sa isang solong array elemento. 

Ano ang Gitnang ng array na ito? Well, ito ay nagsisimula sa 8, ito nagtatapos sa 8, ang Gitnang ay 8. Ay na kung ano ang aming hinahanap para sa? Ang kami ay naghahanap para sa 17? Hindi, kami ay naghahanap para sa 16. Kaya kung umiiral na ito sa array, ito ay dapat na umiiral sa isang lugar sa kaliwa ng kung saan kami ay kasalukuyang ay. Kaya ano pa ang gagawin natin? Well, kami ay itakda ang end point na lamang sa kaliwa ng kasalukuyang midpoint. Kaya makikita namin baguhin ang end point sa 7. Nakikita mo ba kung ano lang nangyari dito, bagaman? Hanapin dito ngayon. 

Start ay mas malaki sa dulo ngayon. Mabisa, ng dalawang dulo ng aming array na tumawid, at ang simula punto ay ngayon pagkatapos ng punto ng pagtatapos. Well, na hindi gumawa ng anumang kahulugan, tama? Kaya ngayon, kung ano ang maaari naming sabihin ay namin magkaroon ng isang sub hanay ng mga laki 0. At sa sandaling kami ay tapat na paraan upang puntong ito, maaari naming ngayon garantiya na elemento na 16 Hindi umiiral sa array, dahil ang start point at end point na tumawid. At kaya ito ay hindi doon. Ngayon, mapapansin na ito ay bahagyang naiiba kaysa sa start point at pagtatapos point sa pagiging pareho. Kung kami ay naghahanap para sa 17, ito ay may ay sa array, at ang start point at end point ng na huling pag-ulit bago tumawid ang mga puntos, Gusto namin nakita ang 17 doon. Ito ay lamang kapag sila ay tatawid na aming makakaya garantiya na ang mga elemento ay hindi umiiral sa array. 

Kaya sabihin kumuha ng isang pulutong ng mas kaunting mga hakbang sa linear paghahanap. Sa pinakamasama kaso sitwasyon, nagkaroon kami sa split up ng isang listahan ng mga elemento n paulit-ulit sa loob ng kalahating upang mahanap ang target, alinman dahil ang target element ay isang lugar sa huling division, o ito ay hindi na umiiral sa lahat. Kaya sa pinakamasama kaso, kami ay may sa maghiwalay ang array-- ang kilala mo? Log ng n beses; tayo upang kunin ang mga problema sa kalahati ng isang tiyak na bilang ng beses. Na bilang ng mga beses ay log n. 

Ano ang pinakamahusay na kaso sitwasyon? Well, sa unang pagkakataon namin kalkulahin ang Gitnang, nakita namin kung ano ang aming hinahanap. Sa lahat ng mga nakaraang mga halimbawa sa binary paghahanap lang kami ay wala sa loob, kung kami ay ay naghahanap ng mga element 15, sana ay natagpuan namin na agad. Iyon ay sa pinakadulo simula. Iyon ay ang Gitnang ng ang unang pagtatangka sa isang split ng isang dibisyon sa binary paghahanap. 

At kaya sa pinakamalala kaso, tumatakbo binary search in log n, na kung saan ay malaki mas mahusay kaysa sa haba ng paghahanap, sa pinakamasama kaso. Sa pinakamahusay na kaso, binary search tumatakbo sa wakas ng 1. Kaya binary paghahanap ay isang pulutong mas mahusay kaysa sa linear paghahanap, ngunit ikaw ay may sa pakikitungo sa proseso ng paghihiwalay muna ang iyong array bago ka makakapag pagkilos ang kapangyarihan ng binary paghahanap. 

Ako Doug Lloyd. Ito ang CS 50.