[Redare a muzicii] 

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, de asemenea, un fel care sortează matrice numita valori. 

Deci, haideți să abordeze căutare. Căutare este în prezent pusă în aplicare ca o căutare liniară, dar puteți face mult mai mult decât atât. Căutare liniară este implementat în O de n timp, care este destul de lentă. Deși, se 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, întreg trei. 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 agendă telefonică la mijloc pagina in saptamana zero. 

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 trei, ac nostru, este mai mic 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, ai dreptate legat pot 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, ce pseudocod arata ca? Ei bine, în timp ce suntem încă în căutarea prin lista și încă mai au elemente la uita-te la, vom lua la mijlocul listei, și compara ca valoare 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 return false deoarece acul cu siguranta nu este în carul cu fân. 

Acum, un lucru elegant despre acest pseudocod în binar de căutare este că acesta poate fi interpretat fie ca o 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 Desigur, dar știu că aceasta este o opțiune dacă doriți să încercați. 

Acum, să ne uităm la fel. Un fel nevoie de o matrice și întreg n, care este dimensiunea matricii. Acum, există diferite tipuri diferite de soiuri, si poti sa te uiti la unele pantaloni scurți pentru demo-uri și explicații. Tipul de retur pentru noastră Funcția de sortare este nulă. Asta înseamnă că nu vom pentru a reveni orice matrice de la fel. Suntem de fapt de gând să schimbe foarte matrice care a fost trecut în noi. 

Și asta e posibil, deoarece matrice sunt transmise prin referință în C. Acum vom a se vedea mai multe despre acest lucru mai târziu, dar diferență esențială între trecere în ceva ca un întreg și trecere într-o matrice, este că atunci când trece într-un întreg, C este doar de gând să face o copie de care întreg și să treacă acesta a funcției. Variabila originală nu va fi modificată odată ce funcția este terminat. Cu o serie, pe de altă parte, este nu de gând să facă o copie, și veți de fapt, să fie editarea foarte matrice în sine. 

Deci, un tip de sortare este un fel de selecție. Un fel de selecție de lucrări pornind de la la început, și apoi voi repeta peste și pentru a găsi cel mai mic element. Și apoi de swap, care mai mic Element cu prima. Și apoi trece la al doilea element , A găsi cele mai mici următoare elemente, și apoi de swap că, odată cu al doilea element în matrice deoarece Primul element este deja sortat. Și așa, atunci veți continua pentru fiecare Element în identificarea mai mici valoare și schimbarea l. 

Pentru I este egal cu 0, foarte primul element a n minus 1, ai de gând să compare fiecare următor valoare, după care și găsească indicele de valoarea minimă. Odată ce ați găsit indicele valorii minime, puteți schimba această valoare de matrice minim și matrice I. 

Un alt tip de fel pe care le puteți să pună în aplicare este balon fel. Deci reiterează bule de sortare peste lista comparând elementele adiacente și schimbarea elementelor care sunt în ordine greșită. Și în acest fel, cel mai mare element va bule până la capăt. Și lista este sortată o dată nu mai elemente au fost schimbate. 

Deci, acestea sunt două exemple de fel algoritmi pe care le puteți pune în aplicare pentru programul de descoperire. După ce ați terminat de sortare, și ai făcut de căutare, ați terminat. Numele meu este Zamyla, iar acest lucru este CS50. 

[Redare a muzicii]