[Powered by Google Translate] [Linearni Traži]
[Patrick Schmid, Sveučilište Harvard]
[This Is CS50.] [CS50.TV]
Tražim je nešto što vjerojatno ne češće nego što mislite.
Očito, svaki put kada otvorite web preglednik
i potraga za web stranice -
ili traži za svoje prijatelje na svoj omiljeni socijalna mreža položaj -
vi ste u potrazi.
No, to je samo mali dio od traženja da se bavite na dnevnoj bazi.
Kada želite da otkrijete da jedan plavu košulju u ormaru,
ili da savršena crvena bluza za tu prigodu,
ste u potrazi.
Kad idete u dućan da ste nikada nije bio na prije,
a vi ste u potrazi za brokule u proizvode prolaz
ste u potrazi.
Ono što svibanj su počeli da se primjetiti
je da, ovisno o tome što ste u potrazi za
ili kako predmeti su organizirani kada ste u potrazi za njima
ima utjecaj na to kako se traži.
Na primjer, ako su vaše košulje visi u ormaru,
vjerojatno možete samo to podići bez puno traži.
Ako ste pod pretpostavkom da morate hodati niz prolaz
dobiti brokulu, vjerojatno morati gledati na svim drugim povrćem
prije vam da brokulu.
Linearni Pretraživanje je primjer jednog takvog potrazi metodom - ili algoritam.
Kao što naziv implicira,
ova metoda traži za stavku u linearno, jedan iza drugoga.
Dakle, kada ste u potrazi na rezultate iz svoje omiljene tražilice
a vi pročitajte dolje na popisu rezultata,
koristite linearni pretraživanje.
Ok. Pogledajmo primjer.
Recimo da imamo popis brojeva - 2, 4, 0, 5, 3, 7, 8 i 1 -
i mi smo u potrazi za broj 0.
Očito, možete samo vidjeti da je 0 u trećoj poziciji.
No, računalni program nije da je sretan.
To samo može "vidjeti" jedan broj u isto vrijeme.
Dakle, s početkom u početku popisa,
to je samo "vidi" je 2.
Program zatim provjerava - je dva jednaka 0?
Očito ne. Tako to ide na sljedeći broj, četiri.
Da li četiri jednaka 0? Nope.
Sljedeći, 0. Ah! Zero je jednaka 0.
Tu smo ga! To je u trećem položaju.
Ok. Pogledajmo neke pseudocode.
To je samo par redaka dugo, ali pogledajmo to jedna linija na vrijeme.
Prvo, neka je definirati funkciju - i mi ćemo ga zovu linearni pretraga -
i to traje dva argumenta - ključ i lepezu.
Ključno je da se vrijednost da smo u potrazi za,
tako da u prethodnom primjeru, koji je bio nula.
Niz je popis brojeva
da ima sve vrijednosti koje ćemo tražiti.
Dakle, ono što želim učiniti je da želimo pogledati -
iz svih položaja, tako da počinje na samom početku niza
til samom kraju niza - tako duljini polja -
pogledati svaki položaj i provjerite svaki.
Dakle, to je ono što je "za" petlja se radi.
I na svakoj poziciji, idemo reći
"Je li to vrijednost u tom trenutnu poziciju jednakom ključu da smo u potrazi za?"
Dakle - u prethodnom primjeru opet, ključ je 0 -
tako da smo se govoreći: "Je li polje na poziciji ja jednaka nuli?"
Ako je, idemo se vratiti 'ja', jer to je trenutna pozicija smo na.
Dakle, u prethodnom primjeru,
da je treće mjesto.
Ako smo prošli kroz cijeli niz
i nismo našli ništa -
pa ajmo reći da smo bili u potrazi za brojem 500
koji jasno nije bio u tom primjeru -
moramo se vratiti nešto,
i da ćemo se vratiti -1.
I mi smo samo vraća -1, jer to je položaj
da ne postoji u polju.
I tako to znači kada vam ga vratiti iz funkcije
ona kaže: "Hm, ok. mislim da nisu pronašli ništa.
Tako da 500 nikada nije bio tamo. "
Lijepo je stvar o linearnom potrazi je da
to će raditi na bilo kojem popisu stavki,
bez obzira na to kako se stavke naredio.
Nije bitno gdje je brokula u proizvode prolaz.
Dokle god hoda niz prolaz od početka do kraja,
vi ste dužni da ga pronaći,
pretpostavljajući dućan nije ponestalo brokule, naravno.
No, to je najveća snaga je također da je najveća slabost.
Recimo da imate popis dvjesto brojeva
koji su razvrstani 1-200.
Ako ste u potrazi za brojem 198,
morate tražiti gotovo cijeli popis brojeva
prije nego što pronađete onu koju tražite.
Mora postojati bolji način!
Budite uvjereni da postoji.
Ali, to je tema za drugi video.
Također, ne uzrujavati!
Samo zato linearno pretraživanje nije najbolje rješenje u svim situacijama,
to ne znači da to ne dolazi u ruci.
Inače, kako bi vam tu brokulu u proizvoditi prolaz?
Moje ime je Patrick Schmid, a ovo je CS50.
[CS50.TV]