>> [Muzikavimo]
>> ZAMYLA CHAN: pirmas dalykas, kurį galėtų pranešimas apie radinį, kad mes jau
yra kodas parašyta mums.
Tai vadinama platinimo kodas.
Taigi mes ne tik raštu mūsų pačių Kodas iš nulio nebėra.
Atvirkščiai, mes užpildant ertmes kai iš anksto esamą kodą.
>> Find.c programa paragina numerius užpildyti kaugė, ieško
kaugė vartotojo pateikta adata, ir tai daroma telefonu rūšiuoti ir
ieškoti, funkcijos apibrėžtos į helpers.c.
Taigi find.c parašyta jau.
Jūsų darbas yra rašyti pagalbininkai.
>> Taigi, ką mes darome?
Mes įgyvendinti dvi funkcijas.
Paieška, kuri grąžina true, jei vertė randama šieno kupetoje, grįžta
false, jei reikšmė yra ne kaugė.
Ir tada mes taip pat įgyvendinant rūšiuoti kuri rūšiuoja masyvas vadinamas vertės.
>> Taigi galime spręsti paiešką.
Paieška šiuo metu įgyvendinama kaip linijinis paieška, bet jūs galite padaryti daug
geriau nei tai.
Linijinis paieška įgyvendinama O n metu, kuris yra gana lėtas.
Nors ji gali ieškoti bet sąrašas duota.
Jūsų darbas yra įgyvendinti dvejetainis paieškos, kuri skaičiuoti laiką O log n.
Tai gana greitai.
>> Tačiau yra nuostata.
Dvejetainiai paieškos gali ieškoti tik per surūšiuotas sąrašus.
Kodėl taip yra?
>> Na pažvelkime pavyzdys.
Atsižvelgiant vertybių masyvas, kaugė, mes ketiname būti ieškote
Pereiti prie adatos.
Ir šiame pavyzdyje, sveikasis skaičius trys.
Taip, kad dvejetainis paieška veikia tai, kad mes palyginti vidurinį vertę
masyvas adata, panašiai kaip mes atidarėme knygutę į vidurį
puslapis nulio savaitę.
>> Taigi palyginus vidurinį vertę adata, galite išmesti arba
kairę arba į dešinę pusę masyvo veržiant savo ribas.
Šiuo atveju, nes trys, mūsų adata, yra mažesnis nei 10, vidurinioji vertė,
teisė riba gali sumažėti.
Bet pabandyti padaryti savo ribas taip griežtai, kaip įmanoma.
Jei vidurinioji vertė yra ne adata, tuomet jūs žinote, kad jums nereikia
įtraukti jį į savo paiešką.
Taigi tu teisus jungiasi gali sugriežtinti Paieškos ribų Truputėlį daugiau,
ir taip toliau ir taip toliau, kol jums rasti adatą.
>> Taigi, ką Pseudocode atrodo?
Na, o mes vis dar ieško per sąrašas ir dar elementai
ieškoti, mes vidurį sąrašo ir palyginkite, kad vidurinės vertę
mūsų adata.
Jei jie vienodi, tada tai reiškia, kad mes rasti adatą ir mes galime
return true.
>> Priešingu atveju, jei adata yra mažesnis nei vidutinio vertė, tai reiškia, kad mes
gali atmesti teisingą pusę, ir tik ieškoti kairėje pusėje masyvo.
Priešingu atveju, mes ieškoti Dešinėje pusėje masyvo.
Ir pabaigoje, jei jūs neturite daugiau elementų paliko ieškoti bet jūs
neradau savo adatą dar, tada jūs return false, nes adata
tikrai nėra šieno kupetoje.
>> Dabar tvarkingas dalykas apie šį Pseudocode dvejetainėje paieškos yra tai, kad jis gali būti
aiškinama kaip arba kartotinis arba grįžtamojo įgyvendinimas.
Taigi būtų grįžtamojo jei vadinamas paieškos funkcija per paiešką
veikti abiejose masyvo pusę.
Mes padengti rekursija tiek vėliau Žinoma, bet žinau, kad tai yra
variantas, jei norite pabandyti.
>> Dabar pažvelkime rūšiuoti.
Rūšiuoti trunka masyvą ir sveikasis skaičius n, kuris yra masyvo dydis.
Dabar yra įvairių tipų dvasia, ir jūs galite pažvelgti į kai
šortai demo ir paaiškinimus.
Grįžimas į mūsų rūšiavimo funkcija klaidinga.
Taigi, tai reiškia, kad mes neketiname grąžinti visą spektrą nuo rūšies.
Mes iš tikrųjų ketiname pakeisti labai matrica, kuri buvo perduota į mus.
>> Ir tai įmanoma, nes matricos priimtas atsižvelgiant į C Dabar mes
vėliau sužinoti daugiau apie tai, bet Esminis skirtumas tarp kitko
kažką panašaus į sveikojo skaičiaus ir artimųjų masyvo, yra tai, kad kai
praeiti sveikasis skaičius, C tik ketina parengia šio sveikojo skaičiaus kopiją ir perduoti
tai ta funkcija.
Originalus kintamasis nebus pakeistas kai funkcija yra baigtas.
Su masyvo, kita vertus, tai nesiruošia daryti kopiją, ir jūs
faktiškai redaguoti labai masyvo pati.
>> Taigi, vieno tipo rūšies yra pasirinkimas rūšiuoti.
Pasirinkimas rūšiuoti veikia pradedant pradžioje, ir tada pakartoti
daugiau ir rasti mažiausią elementą.
Ir tada jūs apsikeitimo kad mažiausias elementas su pirmąja.
Ir tada jums pereiti prie antrojo elemento , Rasti kitas mažiausias
elementas, ir tada sukeisti, kad su Antrasis elementas masyve, nes
pirmasis elementas jau yra išspręstos.
Ir taip, tada jūs ir toliau už kiekvieną elementas nustatant mažiausias
vertė ir keičiant jį.
>> Aš lygi 0, pats pirmas elementas n atėmus 1, jūs ketinate palyginti
kiekvieną kitą vertė po to ir sužinoti minimalios vertės indeksas.
Radę minimali vertė indeksas, galite sukeisti, kad masyvo reikšmę
minimali ir masyvas I.
>> Kitas panašaus tipo, kad jūs galite įgyvendinti yra burbulas rūšiuoti.
Taigi burbulas rūšiuoti kartojasi virš sąrašo palyginti gretimus elementus ir
Swapping elementus, yra neteisinga tvarka.
Ir tokiu būdu, didžiausias elementas bus burbulas iki galo.
Ir sąrašas surūšiuotas kartą ne daugiau elementai buvo sukeistos.
>> Taigi tie du pavyzdžiai rūšiuoti algoritmai, kad galite įgyvendinti dėl
find programa.
Kai baigsite rūšiuoti ir jūs padaryta paiešką, baigsite.
Mano vardas Zamyla, ir tai yra CS50.
>> [Muzikavimo]