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