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