ZAMYLA Chan: L-ewwel ħaġa inti tista ' avviż dwar jsibu hi li aħna diġà jkunu kodiċi miktub għalina. Din tissejjaħ kodiċi distribuzzjoni. Allura aħna mhux biss bil-miktub tagħna stess kodiċi mill-bidu aktar. Pjuttost, aħna qed timla l-vojt f'xi kodiċi pre-eżistenti. 

Il-programm find.c iqajjem għal numri biex timla l-haystack, tfittxijiet- Haystack għal utent sottomessa labra, u dan tagħmlu billi ċċempel it-tip u tiftix, il-funzjonijiet definiti fil helpers.c. Allura find.c hija diġà bil-miktub. Xogħol tiegħek huwa li tikteb helpers. 

Allura dak li qed nagħmlu? Aħna qed timplimenta żewġ funzjonijiet. Search, li jirritorna minnu jekk valur jinstab fil-haystack, jirritornaw falz jekk il-valur huwa mhux fil-haystack. U allura aħna qed timplimenta wkoll sort, li xorta l-array imsejħa valuri. Mela ejja tindirizza search. 

Search hija implimentata bħalissa bħala search lineari. Iżda int tista 'tagħmel ħafna aħjar minn dik. Tfittxija lineari hija implimentata O ta 'n time, li huwa pjuttost bil-mod, għalkemm tista 'tfittex kull lista mogħtija lilha. Xogħol tiegħek huwa li timplimenta tfittxija binarju, li tkun run time O ta 'log n. Li pretty fast. 

Iżda hemm stipulazzjoni. Tfittxija Binarju tista 'tfittex biss permezz ta 'listi magħżula minn qabel. Għaliex huwa li? Well, ejja nħarsu lejn eżempju. Minħabba l-firxa ta 'valuri, il-haystack, aħna qed tmur biex tkun tfittex għal labra, u f'dan il- eżempju, il-integer 3. 

Il-mod li tfittxija binarju jaħdem huwa li inqabblu l-valur medju ta ' il-firxa tal-labra, ferm simili kif aħna fetħet ktieb tat-telefon għall-nofs paġna fil f'Ġimgħa 0. Allura wara tqabbil tal-valur medju biex il-labra, inti tista 'jarmi jew il- xellug jew in-nofs lemini tal-array billi issikkar limiti tiegħek. F'dan il-każ, mit-3, labra tagħna, huwa anqas minn 10, il-valur tan-nofs, il- dritt marbut jistgħu jnaqqsu. 

Iżda jippruvaw jagħmlu limiti tiegħek stretta daqs kemm possibbli. Jekk il-valur tan-nofs mhuwiex il-labra, imbagħad inti taf li inti m'għandekx bżonn li tinkludih fit-tfittxija tiegħek. Allura dritt tiegħek marbuta tista issikka l- limiti tat-tiftix biss ftit żgħira aktar, u hekk u ibqa 'sejjer hekk, sakemm issib labra tiegħek. 

Allura dak li ma l-psewdo kodiċi look like? Well, filwaqt li aħna qed għadhom tfittex permezz il-lista u għad għandhom elementi biex tfittex fil, nieħdu l-nofs tal-lista u jqabblu li valur medju għall-labra tagħna. Jekk dawn qed ugwali, allura dan ifisser konna sabet il-labra, u nistgħu ritorn vera. 

Inkella, jekk il-labra tkun inqas minn il-valur tan-nofs, allura dan ifisser li aħna jista 'jarmi l-nofs tal-lemin u biss tfittxija ix-xellug tal-array. Inkella, aħna ser tfittex il- lemin tal-array. U fl-aħħar, jekk inti ma għandekx xi aktar elementi xellug ta 'tiftix imma int ma sabu labra tiegħek għadhom, allura inti tirritorna falza. Minħabba li l-labra definittivament mhuwiex fil-haystack. 

Issa, ħaġa waħda pulita dwar dan psewdo kodiċi fit-tfittxija binarju huwa li tista ' tiġi interpretata jew bħala iterattiv jew l-implimentazzjoni rikursiv. Għalhekk ikun rikursivi jekk inti imsejħa il-funzjoni ta 'tfittxija fil-search jiffunzjonaw fuq kull nofs il-firxa. Aħna ser ikopru recursion daqsxejn aktar tard fil-kors. Imma nafu li hija possibilità jekk inti tixtieq li jippruvaw.