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