>> 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.