[Glazba svira] 

ZAMYLA Chan: Prva stvar koju ćete Obavijest o otkriću je da smo već su kod napisan za nas. To se zove distribucija code. Dakle, mi ne samo pisanje vlastitih koda od nule više. Umjesto toga, mi smo popunjavanja praznine na neki već postojeći kod. 

Find.c Program traži brojeva popuniti plast sijena, traži plastu sijena za korisnika podnosi iglom, i to čini pozivom vrsta i pretraživanja, funkcije definirane u helpers.c. Dakle find.c je napisano već. Vaš je zadatak napisati pomagače. 

Pa što da radimo? Mi provedbi dvije funkcije. Pretraga, koji vraća true ako je vrijednost nalazi u plastu sijena, povratka false ako je vrijednost Ne u plastu sijena. I onda mi smo također provedbi vrsta koji sortira niz zove vrijednosti. 

Tako ćemo se borila za pretraživanje. Traži trenutno se provodi kao slijedne pretrage, ali vi možete učiniti mnogo bolje od toga. Linearni traži se provodi u O n vremena, što je prilično sporo. Iako, to može pretraživati Popis bilo dano na njega. Vaš posao je da se provede binarni pretragu, koja je pokrenuti vrijeme O iz dnevnika n. To je prilično brzo. 

Ali postoji uvjet. Binary traži se samo traži kroz prethodno sortirani listama. Zašto je to tako? 

Pa pogledajmo primjer. S obzirom na niz vrijednosti, plast, ćemo biti u potrazi za iglu. I u ovom primjeru, cijeli broj tri. Način na koji binarno pretraživanje radi je da Usporedimo srednju vrijednost polje za igle, poput kako otvorili smo imenika na sredini stranica u tjednu nula. 

Dakle, nakon što se usporede srednje vrijednosti igla, možete odbaciti bilo lijeva ili desna polovica niz zatezanjem svoje granice. U tom slučaju, od tri, naša iglu je manje od 10, srednja vrijednost, Pravo granicu može se smanjiti. No, pokušati napraviti svoje granice kao čvrsto što je više moguće. Ako srednja vrijednost nije igla, onda znate da ne trebate uključiti ga u pretraživanje. Dakle, u pravu si granicu može zategnuti search granice samo jedan maleni malo više, i tako dalje i tako dalje sve dok nađete svoj iglu. 

Dakle, ono što ne pseudocode izgledati? Pa, dok smo još uvijek gleda kroz Popis i još uvijek imaju elemente gledati u, uzmemo sredinu ljestvice, i usporediti tu srednju vrijednost naša igla. Ako su oni jednaki, onda to znači da smo pronašao iglu i što možemo povratak istina. 

Inače, ako je igla ispod srednja vrijednost, onda da mi znači može odbaciti desnu polovicu, a samo traži lijevu stranu polja. Inače, mi ćemo tražiti desnoj strani polja. I na kraju, ako ne imati bilo više elemenata ostavili da traži, ali ste nisu pronašli svoj iglu još, onda vam povratak false jer igla definitivno nije u plastu sijena. 

Sada uredan stvar o ovom pseudocode binarno pretraživanje je da to može biti tumačiti kao bilo iterativni ili rekurzivna provedba. Tako da će to biti rekurzivna ako zove pretraživač u potrazi djelovati na bilo polovici polja. Mi ćemo pokriti rekurziju malo kasnije u Naravno, ali znam da je to izbor ako želite probati. 

Sada pogledajmo koje vrste. Sortiranje traje niz i cijeli broj n, što je veličina polja. Sada postoje različiti tipovi sorti, a možete pogledati neke hlačice za demonstracije i objašnjenja. Tip za povratak naših vrsta funkcija je nevažeće. Dakle, to znači da nećemo da se vrate bilo niz od vrste. Mi se zapravo neće promijeniti vrlo Niz koji je donesen u nama. 

I to je moguće jer su nizovi donijela reference u C. Sad ćemo više o tome kasnije, ali Bitna razlika između prolazu u nešto poput cijeli broj i smrti u nizu, je da kada se prođe u cijeli broj, C samo ide na napraviti kopiju tog cijelog broja i proći da funkcije. Izvorna varijabla neće se mijenjati Jednom funkcija završila. S nizom, s druge strane, to Ne ide to napraviti kopiju, a vi ćete zapravo se uređivanje Sam vrlo polje. 

Dakle, jedna vrsta vrste je svojevrsna selekcija. Izbor vrsta djela s početkom u početak, a onda ponoviti tijekom i pronaći najmanji element. I onda zamijeniti ona najmanja Element s prvom. I onda se preselite na drugi element , Naći pored najmanji elementa, a zatim da se zamijeniti s Drugi element u polju, jer Prvi element je već riješeno. I tako onda ste i dalje za svaki element u identificiranju najmanji vrijednost i to zamjenom. 

Jer sam jednako 0, prvi elementa do n minus 1, ideš uspoređivati svaka sljedeća vrijednost nakon toga i pronaći Indeks minimalne vrijednosti. Jednom kada pronađete indeks minimalna vrijednost, možete zamijeniti tu vrijednost niza Minimalna i niz I. 

Druga vrsta vrste koje možete implementirati je mjehurić vrsta. Dakle mjehurić sortirati iterates preko popisa Usporedbom susjedne elemente i zamjene elemenata koji su u pogrešnom redoslijedu. I na ovaj način, po veličini je element će mjehurić na kraju. A popis sortira odjednom više nema elementi su zamijenili. 

Dakle, to su dva primjera vrste algoritmi koji možete provesti za Program otkriće. Nakon što ste završili vrsta, a vi ste obaviti pretragu, gotov si. Moje ime je Zamyla, a to je CS50. 

[Glazba svira]