>> [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]