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