ZAMYLA CHAN: Primul lucru pe care s-ar putea aviz cu privire la descoperire este că noi deja au cod scris pentru noi. Aceasta se numește cod de distribuție. Deci, nu doar scris propria noastră mai cod de la zero. Mai degrabă, suntem completarea golurilor în unele cod pre-existent. 

Programul find.c solicită numere pentru a umple carul cu fân, caută claie de fân pentru un ac de utilizator prezentate, și-l face acest lucru prin apel tip și de căutare, funcții definite în helpers.c. Astfel find.c este scris deja. Treaba ta este de a scrie ajutoare. 

Deci, ce facem? Suntem punerea în aplicare a două funcții. De căutare, care returneaza true daca o valoare se găsește în carul cu fân, revenind false dacă valoarea este nu în carul cu fân. Și apoi vom punere în aplicare a, de asemenea, un fel, care sortează matrice numita valori. Deci, haideți să abordeze căutare. 

Căutare este implementat în prezent ca o căutare liniară. Dar poți să faci mult mai mult decât atât. Căutare liniară este implementat în O de n timp, care este destul de lent, deși poate căuta orice listă dat să-l. Treaba ta este de a implementa căutare binară, care a rulat timp O, de n log. Asta e destul de repede. 

Dar există o prevedere. Binar de căutare poate căuta numai prin liste de pre-sortate. De ce este asta? Ei bine, să ne uităm la un exemplu. Având în vedere o serie de valori, carul cu fân, vom fi uitat pentru un ac, și în acest exemplu, numărul întreg 3. 

Modul în care funcționează binar de căutare este că vom compara valoarea de mijloc a matrice pentru a acului, mai mult ca și cum am deschis o carte de telefon la mijloc Pagina în Săptămâna 0. Deci, după compararea valorii de mijloc a acul, puteți să aruncați fie stânga sau jumătatea din dreapta a matrice prin strângerea limitele impuse. În acest caz, deoarece 3, ac noastră, este mai puțin de 10, valoarea de mijloc, drept legat poate scădea. 

Dar încercați să faceți limite de la fel de bine ca posibil. Dacă valoarea de mijloc nu este acul, atunci știți că nu aveți nevoie să include în căutarea. Deci, chiar dvs. legat poate strânge limite de căutare doar un pic mai mult, și așa mai departe și așa mai departe, până când veți găsi ac ta. 

Deci, ceea ce face pseudo Codul arata ca? Ei bine, în timp ce suntem încă în căutarea prin lista și încă mai au elemente să se uite la, vom lua la mijloc listei și compara că Valoarea medie a ac nostru. Dacă sunt egali, atunci înseamnă că ne-am găsit acul, și putem return true. 

Altfel, dacă acul este mai mică valoarea de mijloc, atunci înseamnă că ne-am se poate renunța la jumătatea din dreapta și doar căutați în partea stângă a tabloului. În caz contrar, vom căuta partea dreapta a matrice. Iar la final, dacă nu aveți nici o mai multe elemente de stânga pentru a căuta, dar te Nu s-au găsit acul încă, atunci vă întoarceți false. Deoarece acul siguranta nu este în carul cu fân. 

Acum, un lucru curat despre acest pseudo cod în căutare binar este că se poate trebuie interpretate în nici un iterativ sau punerea în aplicare a recursiv. Asa ca ar fi recursiv, dacă te-a sunat funcția de căutare în căutarea funcționeze pe fiecare jumătate de matrice. Vom acoperi recursivitate un pic mai târziu în cursul. Dar știu că aceasta este o opțiune dacă doriți să încercați.