>> [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]