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 sortere, 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 for en nål, og i denne eksempel heltallet 3. 

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 telefonbok til midten side i uke 0. 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 3, vår nål, 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å høyre bundet kan stramme søke grensene bare en liten bit mer, og så videre og så videre, inntil du finne nålen. 

Så hva gjør pseudo Koden se ut? Vel, mens vi fortsatt leter gjennom listen og har fortsatt elementer for å se på, tar vi på midten av 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 kanylen absolutt er ikke i høystakken. 

Nå, ett pene ting om denne pseudo kode i binær søk er at det kan tolkes enten som 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 kurset. Men vet at det er et alternativ hvis du har lyst til å prøve.