[Mūzikas atskaņošanai] 

ZAMYLA Chan: Pirmā lieta, jūs varētu Paziņojums par atradumu ir tas, ka mēs jau ir kods rakstīts par mums. To sauc par sadales kodu. Tāpēc mēs esam ne tikai rakstot mūsu pašu kodu no nulles vairs. Drīzāk, mēs esam aizpildot tukšumu dažās iepriekš esošo kodu. 

Find.c Programma piedāvā numurus aizpildīt siena kaudzē, meklē siena kaudzē lietošanas iesniegts adatu, un tas tiek panākts, aicinot veida un meklēt, definēti funkcijas in helpers.c. Tāpēc find.c jau ir uzrakstīts. Tavs uzdevums ir rakstīt palīgi. 

Tātad, ko mēs darām? Mēs īsteno divas funkcijas. Meklēšana, kas atgriež true, ja vērtība ir atrodams siena kaudzē, atgriežoties false, ja vērtība ir ne siena kaudzē. Un tad mēs esam arī īstenošanas veida kas sakārto masīva sauc vērtības. 

Tā ļauj risināt meklēšanu. Meklēšana patlaban tiek īstenots kā lineārā meklēšana, bet jūs varat darīt daudz labāk nekā to. Linear meklēšana tiek īstenota O n laiku, kas ir diezgan lēns. Lai gan tas var meklētu jebkurš saraksts, kas tai piešķirts. Tavs uzdevums ir īstenot bināro meklēšanu, kura darbības laiks O log n. Tas ir diezgan ātri. 

Bet tur ir noteikums. Bināro meklēšanu var tikai meklēt izmantojot iepriekš sakārtoti sarakstos. Kāpēc tā? 

Nu aplūkosim piemēru. Ņemot vērā masīvs vērtībām, siena kaudzē, Mēs ejam, lai meklē adatu. Un šajā piemērā, skaitlis trīs. Veidā, ka bināro meklēšanas darbiem ir tas, ka Salīdzinot vidējo vērtību masīvs uz adatas, līdzīgi kā mēs atvērām Telefonu grāmatu vidū lapa nedēļā nulles. 

Tātad, pēc tam, salīdzinot vidējo vērtību adatu, jūs varat izmest vai nu pa kreisi vai pa labi puse no masīva , pievelkot savas robežas. Šajā gadījumā, tā trīs, mūsu adatas, ir mazāks par 10, vidū vērtību, tiesības robežu var samazināt. Bet mēģināt padarīt jūsu robežas cik stingri vien iespējams. Ja vidū vērtība nav adatu, tad jūs zināt, ka jums nav nepieciešams iekļaut to meklēšanu. Tātad jūs esat tiesības saistoša var savilkt meklēšanas robežas tikai niecīga mazliet vairāk, un tā tālāk, un tā tālāk līdz jums atrast savu adatu. 

Tātad, ko tas pseudocode izskatās? Labi, bet mēs joprojām meklējam cauri sarakstu un joprojām ir elementi izskatās, mēs vidū saraksta, un salīdzināt šo vidējo vērtību Mūsu adatu. Ja viņi ir vienāds, tad tas nozīmē, ka mēs esam atrada adatu un mēs varam atgriezties true. 

Pretējā gadījumā, ja adata ir mazāks nekā vidējā vērtība, tad tas nozīmē, ka mēs var izmest pareizo pusi, un tikai meklēt kreisajā pusē masīvs. Pretējā gadījumā mēs meklētu labajā pusē masīva. Un beigās, ja jums nav nekādu vairāki elementi, pa kreisi, lai meklētu, bet jūs nav atraduši savu adatu vēl, tad jūs atgriezties viltus jo adata noteikti nav siena kaudzē. 

Tagad veikls lieta par šo pseudocode binārā meklēšanas ir, ka tas var būt interpretēt kā nu iteratīvs vai rekursīvs īstenošanu. Tātad tas būtu rekursīvs ja jūs sauc meklēšanas funkcija meklēšanu darbojas uz abām pusēm no masīva. Mēs segtu rekursijas nedaudz vēlāk Protams, bet zina, ka tas ir iespēja, ja jūs vēlaties, lai mēģinātu. 

Tagad aplūkosim veida. Šķirot notiek masīvu un skaitlim n, kas ir lielums masīva. Tagad tur ir dažādi veidi, par veidu, un jūs varat apskatīt dažus šorti demos un skaidrojumus. Atgriešanās tips mūsu šķirošanas funkcija ir spēkā neesošs. Tātad tas nozīmē, ka mēs nebrauksim atgriezties jebkuru masīvs no veida. Mēs esam patiešām gatavojas mainīt ļoti masīvs, kas tika pieņemts par mums. 

Un tas ir iespējams, jo masīvi ir nodots ar atsauci C. Tagad mēs redzēt vairāk par šo vēlāk, bet Būtiskā atšķirība starp garām kaut kā veselam skaitlim, un iet masīva, ir tas, ka tad, kad jūs pāriet veselam skaitlim, C ir tikai gatavojas veikt norakstu no šīs skaitlim un nodot to funkciju. Sākotnējais mainīgais netiks mainīti pēc tam, kad funkcija ir pabeigta. Ar masīva, no otras puses, tas ir nav gatavojas veikt kopiju, un jūs faktiski rediģēšanas ļoti masīvs pati. 

Tāpēc viena veida veida ir atlase kārtošanas. Atlases kārtot darbojas, sākot sākumā, un tad jūs atkārtot vairāk un atrast mazāko elementu. Un tad jūs mijmaiņas ka mazākā elements ar pirmo. Un tad jūs pārvietot uz otro elementu , Atrast nākamais mazākais elements, un tad apmainīt, ka ar Otrs elements masīva, jo pirmais elements ir jau ir sakārtoti. Un tad jūs turpināt katru elements nosakot mazāko vērtība un pārnešana to ārā. 

Es vienāds 0, ļoti pirmais elements līdz n mīnus 1, jūs gatavojas, lai salīdzinātu katru nākamo vērtību pēc tam, un atrast indekss no minimālās vērtības. Tiklīdz jūs atrast minimālo vērtību indeksu, Jūs varat mijmaiņas šo vērtību masīva minimālo un masīvs I. 

Vēl viens veida tips, ka jūs varat īstenot ir burbulis kārtošanas. Tātad burbulis kārtot vairākkārt uzsvērts pār saraksta Salīdzinot blakus elementiem un pārnešana elementus, ir nepareizā secībā. Un tādā veidā, lielākā daļa būs burbulis līdz galam. Un saraksts ir sakārtots pēc tam, kad vairs nav elementi ir samainīti. 

Tātad tie ir divi piemēri veida algoritmi, kas var īstenot atrast programmu. Kad esat pabeidzis kārtot, un jūs esat darīts meklēšanu, jūs esat pabeidzis. Mans vārds ir Zamyla, un tas ir CS50. 

[Mūzikas atskaņošanai]