>> [Musikk spilles]
>> ZAMYLA CHAN: Det første du kanskje varsel om funn er at vi allerede
har kode som er skrevet for oss.
Dette kalles fordelingskode.
Så vi ikke bare skriver vår egen kode fra scratch lenger.
Snarere er vi fylle tomrom i en pre-eksisterende kode.
>> Den find.c program ber om tall å fylle høystakken, søker den
høystakk for en bruker sendt nål, og det gjør dette ved å ringe sortere og
søk, funksjoner definert i helpers.c.
Så find.c er skrevet allerede.
Din jobb er å skrive hjelpere.
>> Så hva gjør vi?
Vi implementere to funksjoner.
Søk, som returnerer true hvis en verdi er funnet i høystakken, retur
usann hvis verdien er ikke i høystakken.
Og så er vi også implementere slags som sorterer tabellen kalt verdier.
>> Så la oss takle søk.
Søk er i dag implementert som en lineær søk, men du kan gjøre mye
bedre enn det.
Lineær søk er implementert i O n tid, noe som er ganske langsom.
Selv om det kan søke noen liste gitt til det.
Din jobb er å implementere binære søk, som har kjøretid O av log n.
Det er ganske fort.
>> Men det er en fastsettelse.
Binære søk kan bare søke gjennom pre-sorterte lister.
Hvorfor er det?
>> Vel la oss se på et eksempel.
Gitt en matrise med verdier, høystakken, vi kommer til å være ute
en nål.
Og i dette eksempelet, heltallet tre.
Måten binære søk fungerer er at Sammenligner vi den midterste verdien av
matrisen til nålen, mye som hvordan vi åpnet en telefonliste til midten
side i uke null.
>> Så etter å sammenligne den midterste verdien til nålen, kan du forkaste enten
venstre eller høyre halvdel av matrisen ved å stramme grenser.
I dette tilfelle, siden tre, vår p, er mindre enn 10, den midterste verdien, den
høyre grense kan reduseres.
Men prøv å gjøre dine grenser så stramt som mulig.
Hvis den midterste verdien ikke nålen da vet du at du ikke trenger å
inkludere det i søket.
Så du har rett bundet kan stramme søke grensene bare en liten bit mer,
og så videre og så videre inntil du finne nålen.
>> Så hva betyr det pseudo se ut?
Vel mens vi fortsatt leter gjennom listen og har fortsatt elementer til
ser på, tar vi midt på listen, og sammenligne det midterste verdien til
vår nål.
Hvis de er like, så det betyr at vi har funnet nålen og vi kan
returnere true.
>> Ellers, hvis nålen er mindre enn den midterste verdien, så det betyr at vi
kan forkaste høyre halvdel, og bare søk på venstre side av tabellen.
Ellers vil vi søke høyre side av tabellen.
Og på slutten, hvis du ikke har noen flere elementer igjen å søke, men du
har ikke funnet din nål ennå, så du return false fordi nålen
definitivt er ikke i høystakken.
>> Nå er en fin ting om dette pseudo i binær-søk er at det kan være
tolkes enten en iterativ eller rekursiv gjennomføring.
Så det ville være rekursiv hvis du heter søkefunksjonen i søket
fungere på hver halvdel av matrisen.
Vi dekker rekursjon litt senere i selvfølgelig, men vet at det er en
alternativ hvis du ønsker å prøve.
>> Nå la oss se på liksom.
Sorter tar en matrise og heltallet n, som er på størrelse med matrisen.
Nå er det ulike typer av former, og du kan se på noen
shorts for demoer og forklaringer.
Returtypen for vår sorteringsfunksjonen er ugyldig.
Så det betyr at vi ikke kommer å returnere noen utvalg fra slag.
Vi blir faktisk kommer til å endre selve array som ble vedtatt i oss.
>> Og det er mulig fordi arrays er vedtatt ved referanse i C. Nå vil vi
se mer om dette senere, men vesentlig forskjell mellom bestått
i noe sånt som et heltall og bestått i en matrise, er at når du
passere i et heltall, er C bare kommer til å lage en kopi av som heltall og bestå
det for funksjonen.
Den opprinnelige variabelen vil ikke endres når funksjonen er avsluttet.
Med en matrise, på den annen side, er det ikke kommer til å lage en kopi, og du vil
faktisk være å redigere veldig matrise seg selv.
>> Så en type slag er utvalget slag.
Utvalget slags fungerer ved å starte på begynnelsen, og deretter du reagere
over og finne det minste elementet.
Og så du bytte det minste elementet med den første.
Og så du flytter til det andre elementet , Finner neste minste
element, og deretter bytte den med den andre elementet i matrisen på grunn
det første element allerede er sortert.
Og så så du fortsetter for hver element i å identifisere den minste
verdi og bytte den ut.
>> For jeg er lik 0, den aller første elementet til n minus en, kommer du til å sammenligne
hver neste verdi etter det og finne indeksen av minimumsverdi.
Når du finner den laveste verdien indeksen, du kan bytte at verdien av matrise
minimum og rekke I.
>> En annen type slag som du kan implementere er boble slag.
Så boble sorterings gjentas over listen sammenligne tilstøtende elementer og
bytte de elementene som er i feil rekkefølge.
Og på denne måten, det største elementet vil boble ut til enden.
Og listen er sortert gang ikke mer elementer har blitt byttet.
>> Så de er to eksempler på slag algoritmer som du kan gjennomføre for
Finn-programmet.
Når du er ferdig med slag, og du har gjort søk, du er ferdig.
Mitt navn er Zamyla, og dette er CS50.
>> [Musikk spilles]