>> [Predvaja glasba]
>> ZAMYLA CHAN: Prva stvar, ki jo morda obvestilo o najdbi je, da smo že
so zapisana koda za nas.
To se imenuje porazdelitev koda.
Torej ne samo pisanje lastnega kodo iz nič več.
Namesto tega smo zapolnjevanje praznin v nekaterih obstoječo kodo.
>> Program find.c vpraša po številkah zapolniti senu, išče
senu uporabniško predložiti iglo, in to počne tako, da kliče vrste in
iskanja, funkcije so opredeljena V helpers.c.
Torej je find.c napisal že.
Vaša naloga je, da napišete pomočnice.
>> Torej, kaj počnemo?
Mi smo za izvajanje dveh funkcij.
Iskanje, ki vrne true, če vrednost se nahaja v senu, vračanje
false, če je vrednost ne v senu.
In potem smo tudi izvajanje vrste ki sortira array imenovano vrednosti.
>> Torej, kaj je dosti iskanje.
Iskanje je trenutno izvaja kot linearno iskanje, vendar lahko veliko naredijo
boljši od tega.
Linearni iskanje se izvaja v O časa, N, pri čemer je zelo počasno.
Čeprav lahko iskanje na katerem koli seznamu dati na to.
Vaša naloga je, da se izvaja binarno iskanje, ki je teči čas O log n.
To je zelo hitro.
>> Ampak tam je določilo.
Binarno iskanje lahko iščete le skozi predhodno razvrščena-seznamov.
Zakaj je tako?
>> Pa si oglejmo primer.
Glede na niz vrednot, senu, bomo morali iskati
iglo.
In v tem primeru celo tri.
Tako, da binarno iskanje deluje, je, da primerjamo srednjo vrednost
matrika z iglo, podobno kot kako smo odprli imenik na sredino
stran v ničelni teden.
>> Torej po primerjavi srednji vrednosti igle, lahko zavržemo bodisi
levo ali desno polovico matrike s poostritvijo svoje meje.
V tem primeru, ker so tri, naš igle, manj kot 10, srednji vrednosti,
Pravica vezan, lahko zmanjša.
Ampak poskusiti, da bi svoje meje tako strogo, kot je mogoče.
Če je srednja vrednost ni igla, potem veste, da vam ni treba, da
jo vključite v vaše iskanje.
Torej imaš vezan, lahko pritrdite išči meje le majhen košček več,
in tako naprej in tako naprej, dokler ste našli iglo.
>> Torej, kaj psevdokoda izgledal?
No, ko smo še vedno gleda skozi seznam in še vedno elemente
poglej v, vzamemo na sredini seznama, in primerjajte to srednjo vrednost
naša igla.
Če so enaki, potem to pomeni, da ste našel iglo in smo lahko
vrne true.
>> V nasprotnem primeru, če je igla manj kot srednja vrednost, potem to pomeni, da
lahko zavržemo desno polovico, in samo iskanje po levi strani matrike.
V nasprotnem primeru bomo iskanje desni strani polja.
In na koncu, če ne boste imeli več elementov pustili za iskanje pa vam
niso našli svojo iglo še ni, potem si vrne false ker igla
zagotovo ni v senu.
>> Sedaj lepo stvar o tem psevdokoda v binarnem iskanju je, da se lahko
razlagati tako, da bodisi ponavljajoč ali rekurzivna izvajanje.
Tako da bi bilo rekurzivni, če se imenuje Iskalna funkcija v iskanju
deluje na obeh polovici matrike.
Pokrili bomo rekurzijo malce kasneje v Seveda, vendar ne vedo, da je
možnost, če želite poskusiti.
>> Zdaj pa si oglejmo vrste.
Razvrsti traja vrsto in celo N, pri čemer je velikost polja.
Sedaj obstaja več različnih vrst z menoj, in si lahko ogledate nekaj
kratke hlače za predstavitve in obrazložitve.
Vrsta donos za naše Funkcija razvrščanja je nična.
To pomeni, da ne bomo za vrnitev vsakega paleto od vrste.
Mi smo dejansko dogaja, da zelo spremenila matrika, ki je bil sprejet v nas.
>> In da je to mogoče zato, ker so nizi s sklicevanjem na C. minilo Zdaj bomo
glej več o tem kasneje, ampak Bistvena razlika med minevanja
nekaj podobnega celo število in prenosu v matriki, je, da ko
prenesti v celo število, C je le, da bo naredite kopijo tega celo število in mimo
je za funkcijo.
Prvotni spremenljivka se ne bo spremenila ko je funkcija končana.
S paleto, na drugi strani pa gre ne dogaja, da bi kopijo, in boste
dejansko urejanje zelo matrika sama.
>> Torej en tip vrste je Izbor sort.
Izbor sortiranje deluje s pričetkom pri začetek, nato pa ponovitev
znova in poiskati najmanjši element.
In potem ste zamenjali da najmanjša element s prvo.
In potem premaknete na drugi element , Našli naslednji najmanjši
element, in nato zamenjali da z Drugi element v matriki, ker
Prvi element je že razporejene.
In tako potem naprej za vsak element pri ugotavljanju najmanjše
vrednost in zamenjavo ven.
>> Kajti enaka 0, zelo prvi element do n minus 1, boste za primerjavo
vsaka naslednja vrednost, po tem in najti Indeks najmanjšo vrednost.
Ko boste našli indeks najnižja vrednost, lahko swap, da je vrednost matrike
Najmanjši in matrika I.
>> Druga vrsta vrste, ki jih lahko izvajati je bubble sort.
Torej bubble vrsta ponovi več na seznamu primerjavo sosednje elemente in
zamenjavo elemente, ki so v napačnem vrstnem redu.
In na ta način, največji del bo mehurček do konca.
In seznam razporejene enkrat več Elementi so bile zamenjane.
>> Torej, to sta dva primera neke algoritmi, ki jih lahko izvajajo za
Program najdba.
Ko končate urejanje, in ste storjeno iskanje, ste končali.
Ime je Zamyla, in to je CS50.
>> [Predvaja glasba]