[Daqq tal-mużika] 

Doug LLOYD: Kull dritt. Allura tfittxija binarja huwa algoritmu nistgħu nużaw biex isibu element ġewwa ta 'firxa. B'differenza tfittxija lineari, dan jirrikjedi kondizzjoni speċjali tintlaħaq qabel, imma hija daqstant aktar effiċjenti jekk din il-kundizzjoni hija, fil-fatt, sodisfatti. 

Allura x'inhu l-idea hawnhekk? huwa firda u conquer. Aħna rridu li jitnaqqas id-daqs ta ' l-erja tfittxija bin-nofs kull darba sabiex isibu għadd fil-mira. Dan huwa fejn din il-kundizzjoni tidħol fis-rwol, għalkemm. Nistgħu lieva biss il-poter ta ' jeliminaw nofs mill-elementi mingħajr ma tħares lejn jekk l-array huwa magħżul. 

Jekk huwa taħlita kompleta up, Ma nistgħux sempliċement minn idejn jarmi nofs mill-elementi, minħabba ma nafux dak li aħna qed rimi. Iżda jekk il-firxa hija magħżula, nistgħu nagħmlu dan, għaliex aħna jafu li kollox lill- xellug ta 'fejn aħna bħalissa għandu jkun inqas mill- valur aħna qed bħalissa. U kollox lill- dritt ta 'fejn ninsabu għandha tkun ikbar mill-valur aħna bħalissa qed tfittex fuq. 

Allura x'inhu l-pseudocode passi għal tfittxija binarja? Aħna irrepeti dan il-proċess sakemm il- firxa jew, kif aħna tipproċedi permezz, sotto arrays, biċċiet iżgħar ta ' il-firxa oriġinali, hija ta 'daqs 0. Ikkalkula l-punt fokali mill-firxa sub attwali. 

Jekk il-valur li qed tfittex hija f'dak element ta 'l-array, stop. Sibtha dan. Li l-kbir. Inkella, jekk il-mira hija inqas minn dak fil-nofs, hekk jekk il-valur aħna qed tfittex għal huwa inqas minn dak li naraw, irrepeti dan il-proċess mill-ġdid, iżda jibdlu l-punt ta 'tmiem, minflok li jkunu l-oriġinali jitlesta firxa sħiħa, li jkun biss lejn ix-xellug ta 'fejn aħna biss ħares. 

Aħna kien jaf li l-nofs kien għoli wisq, jew il-mira kienet inqas mill-nofs, u għalhekk għandhom jeżistu, jekk teżisti fil-livelli kollha fil-firxa, x'imkien ix-xellug tal-punt fokali. U hekk aħna ser jistabbilixxu l-firxa post biss lejn ix-xellug tal-punt tan-nofs bħala l-punt ta 'tmiem ġdid. Bil-maqlub, jekk il-mira hija akbar minn dak fil-grawnd, nagħmlu l-istess eżatt proċess, iżda minflok aħna jibdlu l-punt ta 'tluq li tkun biss għad-dritt ta 'l-punt fokali aħna biss ikkalkolata. U allura, aħna jibdew il-proċess mill-ġdid. 

Ejja Ħares dan, OK? Allura hemm ħafna għaddejjin u hawn fuq, iżda hawnhekk huwa firxa ta 'l-elementi 15. U aħna qed tmur biex jiġu iżżomm rekord ta 'lott għalf aktar dan iż-żmien. Allura fit-tfittxija lineari, konna biss ħsieb dwar mira. Iżda dan iż-żmien irridu jimpurtahom fejn ninsabu tibda tfittex, fejn aħna waqfien tfittex, u x'inhu l-punt tan-nofs mill-firxa attwali. So here we go mal-tfittxija binarja. Aħna pretty ħafna tajba biex tmur, id-dritt? Jien biss se jħott hawn taħt hawn sett ta 'indiċijiet. Dan huwa bażikament biss dak element mill-firxa aħna qed jitkellem dwar. Bil tfittxija lineari, aħna kura, inkwantu aħna bżonn tkun taf kif ħafna Elementi aħna qed mtennija fuq, imma aħna ma attwalment kura liema element aħna bħalissa qed tfittex fuq. Fit-tfittxija binarja, nagħmlu. U hekk dawn huma biss hemm bħala gwida ftit. 

Allura nistgħu tibda, id-dritt? Ukoll, ma pjuttost. Ftakar dak li għidt dwar tfittxija binarja? Aħna ma tistax tagħmel dan fuq firxa mhux magħżul jew inkella, aħna ma tiggarantixxi li l- ċerti elementi jew valuri ma jkunux jkunu aċċidentalment skartati meta aħna biss tiddeċiedi li tinjora nofs il-firxa. 

Allura pass wieħed bil-tfittxija binarja huwa jrid ikollok firxa magħżula. U tista 'tuża kwalunkwe mill-għażla algoritmi konna tkellem dwar li ikollok biex dik il-pożizzjoni. Allura issa, aħna qed f'pożizzjoni fejn nistgħu jwettaq tfittxija binarja. 

Mela ejja irrepeti l-proċess pass pass u jżomm rekord ta 'dak li qed jiġri kif immorru. Allura l-ewwel għandna bżonn tagħmel hu li jikkalkulaw punt tan-nofs tal-firxa attwali. Well, aħna ser ngħidu aħna, l-ewwel kollha, tfittex għall-valur 19. Aħna qed jippruvaw isibu l-numru 19. L-ewwel element ta 'din array tinsab fil-indiċi żero, u l-aħħar element ta 'dan array tinsab fil-indiċi 14. U hekk aħna ser sejħa dawk bidu u t-tmiem. 

Allura aħna jikkalkulaw l-punt fokali minn żżid 0 plus 14 diviż bl 2; punt tan-nofs pjuttost sempliċi. U nistgħu ngħidu li punt tan-nofs issa hija ta '7. Allura huwa 15 dak li aħna qed tfittex? Le, mhuwiex. Aħna qed infittxu 19. Iżda nafu li 19 huwa akbar minn dak li sibna fil-nofs. 

Allura dak li nistgħu nagħmlu huwa jibdlu l-punt ta 'tluq li jkun biss għad-dritt ta 'l- punt tan-nofs, u rrepeti l-proċess mill-ġdid. U meta nagħmlu dan, aħna issa jiġifieri l- punt ta 'tluq ġdid huwa post array 8. Dak li konna effettiv isir huwa kollox injorati ix-xellug tal-15. Imxejna eliminati nofs tal-problema, u issa, minflok li tfittxija aktar minn 15-elementi fil-firxa tagħna, aħna biss għandek tfittex aktar minn 7. Allura 8 huwa l-punt ta 'tluq ġdid. 14 għadu l-punt ta 'tmiem. 

U issa, aħna jmorru fuq dan mill-ġdid. Aħna tikkalkula l-punt fokali ġdid. 8 plus 14 huwa 22, diviż bi 2 huwa 11. Huwa dan dak li aħna qed tfittex? Le, mhuwiex. Aħna qed tfittex għal valur li l- inqas minn dak li aħna biss sabu. Allura aħna qed tmur biex jirrepeti il-proċess mill-ġdid. Aħna ser jibdlu l-punt ta 'tmiem għal tkun biss għall-xellug tal-punt tan-nofs. Għalhekk il-punt aħħari ġdida ssir 10. U issa, dak l-uniku parti tal l-array għandna biex sort permezz. Allura aħna għandna issa eliminati 12 tal-elementi 15. Aħna nafu li jekk 19 teżisti fil-firxa, it għandha teżisti x'imkien bejn element numru 8 u element numru 10. 

Allura aħna jikkalkulaw l-punt fokali ġdid mill-ġdid. 8 flimkien ma '10 huwa 18, diviż bi 2 huwa ta' 9. U f'dan il-każ, ħarsa, il- mira huwa fil-nofs. Sibna eżattament dak li aħna qed tfittex. Nistgħu tieqaf. Lestejna b'suċċess tfittxija binarja. Kull dritt. Allura nafu dan algoritmu xogħlijiet jekk il-mira hija x'imkien ġewwa tal-firxa. Taħdem din algoritmu jekk il-mira ma tkunx fil-firxa? Well, ejja nibdew it għal darb'oħra, u dan iż-żmien, ejja tfittex l-element 16, li viżwalment nistgħu naraw ma teżistix kullimkien fid-firxa. 

Il-punt bidu hija għal darb'oħra 0. Il-punt aħħari huwa ġdid 14. Dawn huma l-indiċi ta 'l-ewwel u Elementi aħħar tal-firxa sħiħa. U aħna ser jgħaddu mill-proċess aħna biss marru permezz darb'oħra, jippruvaw isibu 16, anke jekk viżwalment, nistgħu diġà tell li mhuwiex ser ikun hemm. Aħna biss jixtiequ jagħmlu ċert li din algoritmu se, fil-fatt, għadhom jaħdmu b'xi mod u mhux biss leave us staġnati fi loop infinita. 

Allura x'inhu l-pass ewwel? Ikkalkula l-punt fokali mill-firxa attwali. X'inhu l-punt tan-nofs mill-firxa attwali? Ukoll, huwa 7, id-dritt? 14 plus 0 diviż bi 2 hija ta '7. Huwa 15 dak li aħna qed tfittex? No Huwa pjuttost qrib, iżda aħna qed tfittex għal valur kemmxejn akbar minn dak. 

Allura aħna nafu li huwa għaddej biex jkun imkien ix-xellug tal-15. Il-mira hija akbar minn x'hemm fil-punt tan-nofs. U hekk aħna waqqafna l-punt ġdid bidu tkun biss għad-dritt tal-nofs. Punt tan-nofs huwa attwalment 7, so ejja ngħidu l-punt bidu ġdid huwa 8. U dak li aħna stajt effettivament isir mill-ġdid huwa injorat in-nofs tax-xellug kollu tal-firxa. 

Issa, aħna irrepeti l- proċess wieħed aktar ħin. Ikkalkula l-punt fokali ġdid. 8 plus 14 huwa 22, diviż bi 2 huwa 11. Hija ta '23 dak li aħna qed tfittex? Sfortunatament, l-ebda. Aħna qed tfittex għal valur li hija inqas minn 23. U hekk f'dan il-każ, aħna qed tmur li jibdlu l-punt ta 'tmiem li jkun biss għall-xellug tal-punt fokali attwali. Punt tan-nofs attwali hija 11, u hekk aħna ser jiffissaw il-punt aħħari ġdid għall-ħin li jmiss immorru permezz ta 'dan il-proċess sa 10. 

Għal darb'oħra, aħna jgħaddu mill-proċess mill-ġdid. Ikkalkula l-punt fokali. 8 flimkien ma '10 diviża bi 2 huwa ta' 9. Huwa 19 dak li aħna qed tfittex? Sfortunatament, l-ebda. Aħna qed għadhom tfittex numru inqas minn dik. Allura aħna ser jibdlu l-punt ta 'tmiem dan il-ħin li jkun biss għall-xellug tal-punt fokali. Punt tan-nofs huwa attwalment 9, sabiex il-punt aħħari se jkun 8. U issa, aħna qed tfittex biss fi array element wieħed. 

X'inhu l-punt fokali ta 'din array? Ukoll, huwa jibda fil 8, it jintemm 8, il-punt fokali huwa 8. Hija li dak li aħna qed tfittex? Are we tfittex 17? Le, aħna qed infittxu 16. Mela jekk teżisti fil-firxa, għandu jeżisti x'imkien lejn ix-xellug ta 'fejn aħna bħalissa. Allura dak li aħna se jagħmlu? Well, aħna ser jiffissaw il-punt aħħari li jkun biss għall-xellug tal-punt fokali attwali. Allura aħna ser jibdlu l-punt ta 'tmiem għal 7. Inti tara dak biss ġara hawn, għalkemm? Look up hawn issa. 

Bidu issa huwa akbar minn tarf. Effettivament,-żewġt itruf tal-firxa tagħna jkunu qasmu, u l-punt ta 'tluq huwa issa wara l-punt ta 'tmiem. Ukoll, li ma jagħmel ebda sens, id-dritt? Allura issa, dak li nistgħu ngħidu huwa li aħna jkollhom firxa sub-daqs 0. U ladarba aħna qed gotten li dan il-punt, nistgħu issa jiggarantixxu li l-element 16 ma teżistix fil-firxa, minħabba li l-punt ta 'tluq u l-punt aħħari qasmu. U dan mhuwiex hemmhekk. Issa, avviż li din hija kemmxejn differenti mill-punt ta 'tluq u tat-tmiem punt huma l-istess. Jekk aħna kien infittxu għall-17, huwa jkollu kien fil-firxa, u l-punt bidu u l-punt tmiem ta 'din l-aħħar iterazzjoni qabel dawn il-punti qasmu, aħna sabu 17 hemmhekk. Huwa biss meta jaqsmu li nistgħu jiggarantixxu li l-element ma jeżistu fil-firxa. 

Mela ejja tagħti ħafna inqas passi minn tfittxija lineari. Fil-agħar każ, kellna li jifred lista ta 'elementi n ripetutament fil nofs biex isibu l-mira, jew għaliex l-element mira se tkun x'imkien fl-aħħar diviżjoni, jew ma jeżistix għal kollox. Allura fl-agħar każ, irridu jinqasam l-array-- do you know? Log ta 'drabi n; aħna jkollhom biex inaqqsu l-problema fil nofs ċertu numru ta 'drabi. Dak in-numru ta 'drabi huwa log n. 

X'inhu l-aħjar xenarju? Ukoll, il-ħin ewwel aħna tikkalkula l-punt fokali, insibu dak li aħna qed tfittex. B'kollox 'qabel eżempji fuq tfittxija binarja konna biss marret fuq, jekk kellna qed tfittex l-element 15, aħna sabu li immedjatament. Dan kien fil-bidu nett. Dan kien il-punt tan-nofs ta ' l-ewwel tentattiv ta qasma ta 'diviżjoni fit-tfittxija binarja. 

U hekk fl-agħar każ, tfittxija binarja runs fil log n, li hija sostanzjalment aħjar minn tfittxija lineari, fl-agħar każ. Fl-aħjar każ, binarja tfittxija runs fil omega-1 ta '. Allura tfittxija binarju huwa ħafna aħjar minn tfittxija lineari, iżda inti għandek biex jittrattaw mal-proċess ta ' issortjar firxa tiegħek l-ewwel qabel inti tista jwieżen l-qawwa ta 'tfittxija binarja. 

Jien Doug Lloyd. Dan huwa CS 50.