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 se trenutno provode kao linearni pretragu. No, možete napraviti mnogo bolje od toga. Linearni traži se provodi u O n vrijeme, što je prilično spora, iako može tražiti bilo koji popis s obzirom na to. 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 to Primjerice, cijeli broj 3. 

Način na koji binarno pretraživanje radi je da Usporedimo srednju vrijednost polje za igle, poput kako otvorili smo telefonski imenik na sredini stranica u tjednu 0. 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 3, naša igla 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, vaše pravo dužni može zategnuti search granice samo jedan maleni malo više, i tako dalje i tako dalje, sve dok nađete svoj iglu. 

Pa što ne pseudo Kod izgledati? Pa, dok smo još uvijek gleda kroz Popis i još uvijek imaju Elementi za gledati u, uzmemo u sredini liste i usporedite to srednja vrijednost našem igle. Ako su oni jednaki, onda to znači da smo pronašao iglu, a možemo povratak istina. 

Inače, ako je igla ispod srednja vrijednost, onda da mi znači može odbaciti desnu polovicu i 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 ste se vratili lažna. Zbog igla svakako Nije u plastu sijena. 

Sada, jedan uredan stvar o ovom pseudo Kod u binarnom pretraživanje je da je to moguće 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 Rekurzije malo kasnije u tijeku. Ali znam da je to opcija Ako želite isprobati.