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örs för närvarande 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 det kan 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 efter en nål, och i detta Exempelvis heltalet 3. 

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 0. 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 3, 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å din rätt bunden kan dra åt sökning bounds bara en liten bit mer, och så vidare och så vidare, till dess du hittar din nål. 

Så vad gör pseudo koden se ut? Tja, medan vi fortfarande letar igenom listan och fortfarande ha faktorer att titta in, tar vi i mitten av listan och jämföra det mitt värde 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 returnerar falskt. Eftersom nålen definitivt är inte i höstacken. 

Nu, en snygg sak om denna pseudo koden i binär sökning är att den kan 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 kursen. Men vet att det är ett alternativ Om du vill prova.