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