ZAMYLA CHAN: Den første ting du måske bekendtgørelse om fund er, at vi allerede have kode skrevet til os. Dette kaldes fordeling kode. Så vi ikke bare skrive vores egen kode fra bunden længere. Snarere, vi udfylder hulrum i nogle eksisterende kode. 

Det find.c programmet beder for tal at fylde høstak, søger høstak for en bruger indsendte nål, og det gør dette ved at kalde sortere og søgning, funktioner defineret i helpers.c. Så find.c er skrevet allerede. Dit job er at skrive hjælpere. 

Så hvad gør vi? Vi gennemføre to funktioner. Søg, som returnerer true, hvis en værdi er fundet i høstakken, vender tilbage falsk, hvis værdien er ikke i høstakken. Og så er vi også gennemføre slags, som sorterer array kaldet værdier. Så lad os tage fat søgning. 

Søg i øjeblikket gennemføres som en lineær søgning. Men du kan gøre meget bedre end det. Lineær søgning er implementeret i O n tid, hvilket er ret langsomt, selv om den kan søge enhver liste, det fik. Dit job er at implementere binær søgning, der har kørt tid O af log n. Det er temmelig hurtigt. 

Men der er en bestemmelse. Binær søgning kan kun søge gennem pre-sorterede lister. Hvorfor er det? Nå, lad os se på et eksempel. I betragtning af en matrix af værdier, høstak, vi kommer til at være på udkig efter en nål, og i denne eksempel heltal 3. 

Den måde, at binær søgning værker er, at Sammenligner vi den midterste værdi af array til nålen, meget gerne, hvordan vi åbnede en telefonbog til midten side i uge 0. Så efter sammenligning af den midterste værdi til nålen, kan du kassere enten venstre eller højre halvdel af array ved at stramme dine grænser. I dette tilfælde, idet 3 vores nål, er mindre end 10, den midterste værdi, højre bundet kan falde. 

Men prøv at gøre dine grænser så stramt som muligt. Hvis den midterste værdi ikke er den nål, så ved du at du ikke behøver at medtage den i din søgning. Så din højre grænse kan stramme den søgning bounds bare en lille smule mere, og så videre og så videre, indtil du finder din nål. 

Så hvad gør pseudo kode se ud? Nå, mens vi leder stadig igennem listen og stadig have elementer til at se på, tager vi den midterste af listen, og sammenligne det midterste værdi til vores nål. Hvis de er lige, så det betyder, at vi har fundet nålen, og vi kan returnere sandt. 

Ellers, hvis nålen er mindre end den midterste værdi, så det betyder, at vi kan skille den højre halvdel og bare søge i venstre side af matrixen. Ellers vil vi søge højre side af matrixen. Og til sidst, hvis du ikke har nogen flere elementer tilbage til søgning, men du har ikke fundet nålen endnu, så du vender tilbage falsk. Da nålen helt er ikke i høstakken. 

Nu, en pæn ting om denne pseudo kode i binær søgning er, at det kan tolkes som enten en iterativ eller rekursive gennemførelse. Så det ville være rekursiv hvis du kaldte søgefunktionen i søgningen kan fungere på hver halvdel af matrixen. Vi dækker rekursion lidt senere i kurset. Men ved, at det er en mulighed hvis du gerne vil prøve.