[Daqq tal-mużika] 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. Fittex bħalissa hija implimentata bħala tfittxija lineari, imma int tista 'tagħmel ħafna aħjar minn dik. Tfittxija lineari hija implimentata O ta 'żmien n, 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 l-eżempju, n-numru sħiħ tlieta. 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 phonebook għall-nofs paġna żero ġimgħa. 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ż, la darba tlieta, 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 int dritt bound 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 l pseudocode look like? Well filwaqt li aħna qed għadhom tfittex permezz il-lista u għad għandhom l-elementi għall- tħares, nieħdu l-nofs tal-lista, u jqabblu dak il-valur medju biex labra tagħna. Jekk dawn qed ugwali, allura dan ifisser konna sabu l-labra u nistgħu ritorn vera. Inkella, jekk il-labra tkun inqas minn il-valur tan-nofs, allura dan ifisser li aħna jistgħu jeħilsu in-nofs lemini, 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 għadu tiegħek, allura inti ritorn foloz għaliex il-labra definittivament mhux fil-haystack. Issa ħaġa pulita dwar dan pseudocode fit-tfittxija binarju huwa li tista 'tkun 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- naturalment, iżda nafu li dan huwa għażla jekk inti tixtieq li jippruvaw. Issa ejja nħarsu lejn tip. Sort jieħu firxa u n-numru sħiħ n, li huwa d-daqs tal-array. Issa hemm tipi differenti varji ta 'tipi, u inti tista' tħares lejn xi xorts għall demos u spjegazzjonijiet. It-tip ritorn għall tagħna funzjoni sort huwa null. Allura dan ifisser li aħna ma tkunx qed tmur jibagħtu lura kull array minn tip. Aħna fil-fatt se jibdlu l-ħafna array li kienet għaddiet fil us. U li jista 'jkun minħabba arrays huma għadda b'riferenza C. Issa aħna ser tara aktar dwar din aktar tard, iżda l- differenza essenzjali bejn tgħaddi fil xi ħaġa simili integer u t-trasferiment fil-firxa, hija li meta inti jgħaddu integer, C huwa biss se jagħmel kopja ta 'dak integer u jgħaddu lill-funzjoni. Il-varjabbli oriġinali mhux se tinbidel ladarba l-funzjoni huwa lest. Ma 'firxa, min-naħa l-oħra, huwa mhux se tagħmel kopja, u tkun taf attwalment jiġu editjar ħafna array innifsu. Allura tip wieħed ta 'tip huwa t-tip ta 'għażla. Il sort għażla jaħdem billi jibda il-bidu, u allura inti jtenni fuq u jsibu l-element iżgħar. U allura inti tpartit li iżgħar element bl-ewwel wieħed. U allura inti timxi għat-tieni element , Isibu l-iżgħar li jmiss element, u mbagħad tpartit li bl- tieni element fil-firxa minħabba l-ewwel element huwa diġà magħżula. U hekk allura inti tkompli għal kull element fl-identifikazzjoni l-iżgħar valur u jagħmlu skambju out. Għall I ikun egwali għal 0, l-ewwel element li n minus 1, int ser iqabblu kull valur li jmiss wara dik u jsibu l-indiċi tal-valur minimu. Ladarba ssib l-indiċi tal-valur minimu, inti tista 'tpartit li l-valur tal-firxa firxa minima u I. Tip ieħor ta 'tip li inti tista' jimplimentaw huwa tip bubble. Allura ttenni sort buzzieqa fuq il-lista jitqabblu elementi biswit u iskambji l-elementi li huma fl-ordni żbaljata. U b'dan il-mod, l-akbar element se bubble sa l-aħħar. U l-lista huwa magħżul darba mhux aktar elementi ġew skambjati. Għalhekk dawn huma żewġ eżempji ta 'tip algoritmi li inti tista 'timplimenta għall- il-programm ssib. Ladarba inti finitura sort, u inti stajt jsir tiftix, int lest. Jisimni Zamyla, u dan huwa CS50. [Daqq tal-mużika]