[MUSIK SPELA] 

ZAMYLA CHAN: Det första du kanske meddelande om fyndet är att vi redan har kod skriven för oss. Detta kallas distributionskoden. Så vi inte bara skriva vår egen koda från grunden längre. I stället ska vi fylla i tomrummen i någon befintlig kod. 

Den find.c Programmet frågar efter siffror att fylla höstacken, söker höstack för en användare lämnade nål, och den gör det genom att ringa sortera och sökning, funktioner definierade i helpers.c. Så find.c är redan skrivet. Ditt jobb är att skriva hjälpare. 

Så vad gör vi? Vi ska genomföra två funktioner. Sök, som returnerar true om ett värde påträffas i höstacken, återvänder false om värdet är inte i höstacken. Och då vi genomför också sortera som sorterar arrayen kallas värden. 

Så låt oss ta itu sökning. Sök för närvarande genomförs som en linjär sökning, men du kan göra mycket bättre än så. Linjär sökning genomförs i O n tid, vilket är ganska långsam. Även om, kan det söka någon lista som ges till det. Ditt jobb är att implementera binär sökning, som har körtid O i log n. Det är ganska snabbt. 

Men det finns en bestämmelse. Binär sökning kan endast söka genom pre-sorterade listor. Varför är det? 

Nåväl låt oss titta på ett exempel. Givet en matris med värden, höstacken, vi kommer att vara ute för en nål. Och i detta exempel, heltalet tre. Det sätt som binär sökning fungerar är att vi jämför det mittersta värdet av arrayen till nålen, ungefär som hur Vi öppnade en telefonbok till mitten sida i vecka noll. 

Så efter att ha jämfört det mittersta värdet till nålen, kan du kasta antingen vänstra eller den högra halvan av matrisen genom att dra dina gränser. I det här fallet, sedan tre, vår nål, är mindre än 10, det mittersta värdet, den rätt bunden kan minska. Men försök att göra dina gränser så tätt som möjligt. Om det mittersta värdet är inte av nålen, då vet du att du inte behöver inkludera det i din sökning. Så du har rätt bunden kan dra åt sökning bounds bara en liten bit mer, och så vidare och så vidare till dess att du hittar din nål. 

Så vad pseudokod ut? Väl när vi letar fortfarande igenom listan och fortfarande har element till titta in, tar vi i mitten av listan, och jämför det mittersta värdet till vår nål. Om de är lika, då det innebär att vi har hittade nålen och vi kan return true. 

Annars, om nålen är mindre än det mittersta värdet, då det innebär att vi kan kasta den högra halvan, och bara söka den vänstra sidan av matrisen. I annat fall kommer vi att söka på höger sida av kedjan. Och i slutet, om du inte har några fler element kvar att söka, men du har inte hittat din nål ännu, då du return false eftersom nålen definitivt inte i höstacken. 

Nu en snygg sak om denna pseudo i binär sökning är att det kan vara tolkas som antingen en iterativ eller rekursiv genomförande. Så det skulle vara rekursiv om du heter sökfunktionen i sökandet fungera på vardera halvan av matrisen. Vi täcker rekursion lite senare i naturligtvis, men vet att det är en alternativet om du vill prova. 

Nu ska vi titta på sort. Sortera tar en matris och heltalet n, vilket är storleken på matrisen. Nu finns det flera olika typer av slag, och du kan titta på några shorts för demos och förklaringar. Retur typ för vår sorteringsfunktionen är ogiltig. Så det betyder att vi inte kommer att återvända någon array från slag. Vi ska faktiskt går att förändra mycket array som leddes in oss. 

Och det är möjligt eftersom arrayer är passerade genom hänvisning i C. Nu ska vi se mer om detta senare, men det väsentlig skillnad mellan passerande i något som liknar ett heltal och passerar i en matris, är att när man passera i ett heltal, är C bara att göra en kopia av detta heltal och passera det till funktionen. Den ursprungliga variabeln ändras inte när funktionen är slutförd. Med en array, å andra sidan, är det inte att göra en kopia, och du kommer faktiskt redigera mycket array själv. 

Så en typ av slag är urvals sort. Valet sortera fungerar genom att starta vid början, och sedan iterera över och hitta det minsta elementet. Och sedan byta det minsta element med den första. Och då du flyttar till det andra elementet , Hitta den näst minsta elementet, och sedan byta den med andra element i arrayen eftersom det första elementet är redan sorterade. Och så då fortsätter för varje elementet i att identifiera den minsta värde och byta ut den. 

För jag är lika med 0, den allra första elementet till n minus 1, du kommer att jämföra varje nästa värde efter det och hitta indexet för det minsta värdet. När du hittar det minsta värdet index, du kan byta det värdet av array minimum och array I. 

En annan typ av slag som du kan genomföra är bubbla sortera. Så bubbla sortera itererar över listan jämföra intilliggande element och byta de delar som är i fel ordning. Och på detta sätt, det största elementet kommer bubbla till slutet. Och listan sorteras en gång inte mer delar har bytts. 

Så de är två exempel på slag algoritmer som du kan genomföra för fyndet programmet. När du är klar sorterar, och du har gjort sökningen, är du klar. Mitt namn är Zamyla, och detta är CS50. 

[MUSIK SPELA]