[Musikgengivelse] 

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 et 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 ganske langsomt. Selv kan den 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? 

Jamen så 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 dette eksempel, heltallet tre. 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 åbnede vi en telefonbog til midten side i uge nul. 

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, da tre 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å du har ret bundet 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 betyder det pseudokode se ud? Nå, mens vi stadig kigger gennem listen og stadig have elementer til kigge i, tager vi midt på 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 lige 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 return false fordi nålen absolut ikke er i høstakken. 

Nu er en pæn ting om dette pseudokode i binær søgning er, at det kan være tolkes 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 naturligvis, men ved, at det er et mulighed, hvis du gerne vil prøve. 

Lad os nu se på slags. Sorter tager et array og heltal n, som er størrelsen af ​​matrixen. Nu er der forskellige typer slags, og du kan se på nogle shorts til demoer og forklaringer. Afkastet type til vores slags funktion er ugyldig. Så det betyder, at vi ikke kommer at returnere eventuelle vifte af slags. Vi er faktisk kommer til at ændre den meget array, der blev vedtaget i os. 

Og det er muligt, fordi arrays er sendes som reference i C. Nu vil vi se mere om dette senere, men væsentlig forskel mellem forbigående i noget som et heltal og passerer i et array, er, at når du passere i et heltal, C bare kommer til at lave en kopi af heltal og videregive det til funktionen. Den oprindelige variabel vil ikke blive ændret når funktionen er færdig. Med et array på den anden side er det ikke kommer til at lave en kopi, og du vil faktisk redigere meget matrix selv. 

Så en form for sortering er udvælgelse slags. Udvælgelsen sortere fungerer ved at starte på starten, og så skal du gentage igen og finde det mindste element. Og så skal du bytte at mindste elementet med den første. Og så skal du flytte til det andet element Finder den næstmindste element og derefter swap at med andet element i array, fordi det første element allerede er sorteret. Og så så du fortsætter til hver element i at identificere den mindste værdi og bytte det ud. 

For jeg er lig med 0, det allerførste element til n minus 1, er du nødt til at sammenligne hver næste værdi efter det og finde indekset for den mindste værdi. Når du finder den mindste værdi indekset, du kan bytte, at værdien af ​​matrix minimum og matrix I. 

En anden type af slags, som du kan redskabet er boble slags. Så boble sortere gentager over listen sammenligning af tilstødende elementer og bytte de elementer, der er i den forkerte rækkefølge. Og på denne måde, det største element vil boble til enden. Og listen er sorteret engang ikke mere elementer er blevet byttet. 

Så det er to eksempler på sortering algoritmer, som du kan gennemføre for Find programmet. Når du er færdig sortere, og du har gjort søgning, er du færdig. Mit navn er Zamyla, og det er CS50. 

[Musikgengivelse]