[Powered by Google Translate] [Linear Otsing]
[Patrick Schmid, Harvard University]
[See on CS50.] [CS50.TV]
Otsimine on midagi, mida sa ilmselt teha sagedamini kui te arvate.
Ilmselt iga kord, kui avada veebibrauseris
ja otsida veebilehe -
või otsi oma sõpru oma lemmik suhtlusvõrgustik -
otsite.
Aga see on ainult väike osa otsimine, mida te teete iga päev.
Kui soovite leida, et üks sinine särk kapis,
või et ideaalne punane pluus jaoks sündmus,
mida te otsite.
Kui te lähete poodi, et te pole kunagi olnud enne,
ja otsite brokkoliga toota vahekäiku
mida te otsite.
Mida olete hakanud märkama
on see, et sõltuvalt sellest, mida sa otsid
või kuidas esemed on korraldatud kui otsite neid
see mõjutab, kuidas otsida.
Näiteks, kui teie särgid ripuvad kapis,
saab ilmselt lihtsalt korja see välja ilma palju otsida.
Kui sa eeldades, et teil on kõndida mööda vahekäiku
saada brokoli, siis ilmselt peame vaatama kõik muud köögiviljad
enne kui leiad, et brokkoli.
Lineaarne Otsing on näide ühe sellise otsingu meetod - või algoritm.
Nagu nimigi viitab,
Selle meetodi otsima objekti lineaarselt, üksteise järel.
Niisiis, kui te vaatate tulemusi oma lemmik otsingumootor
ja sa loed ette nimekirja tulemusi,
sa kasutad lineaarset otsing.
Okei. Vaatame näiteks.
Ütle meil Arvuloend - 2, 4, 0, 5, 3, 7, 8 ja 1 -
ja me otsime arvu 0.
Ilmselt saate näha, et 0 on kolmandas asendis.
Aga arvutiprogramm ei ole nii õnnelik.
See saab olla ainult "näha" üks number korraga.
Niisiis, alustades alguses nimekirja,
see ainult "näeb" 2.
Programm siis kontrollib - on 2 võrdub 0?
Ilmselt mitte. Nii see läheb edasi järgmise numbri, 4.
Kas 4 võrdset 0? Nope.
Järgmise üks, 0. Ah! Null on võrdne 0-ga.
On meil seda! See on kolmandal kohal.
Okei. Vaatame mõned pseudokoodi.
See on ainult paar rida pikk, kuid vaatame siis üks rida korraga.
Esiteks, ärgem defineerime funktsiooni - ja me nimetame seda lineaarne otsing -
ja see võtab kaks argumenti - võti ja massiivi.
Oluline on, et raha, mida me otsime,
nii eelmises näites, et oli null.
Massiiv on nimekiri numbrid
, mis on kõik väärtused, mida me hakkame otsima.
Niisiis, mida me tahame teha, on me tahame vaadata -
kõik seisukohad, nii algab algusest massiivi
til päris lõpus massiiv - nii pikkus array -
pilk iga positsiooni ja vaadata igaüks.
Nii see on, mida see "eest" loop teeb.
Ja igas asendis, me ei kavatse öelda
"Kas see on väärtus, et praegune olukord võrdne võti, et me otsime?"
Nii et - eelmise näite, võti oli 0 -
nii me ütleme "Kas massiivi positsioonis i võrdne nulliga?"
Kui on, me läheme tagasi "i", sest see on hetkeseis me oleme.
Niisiis, eelmises näites,
see oli kolmandal kohal.
Kui me oleme läbi käinud kogu massiivi
ja me ei leidnud midagi -
nii oletame, et otsisime arv 500
mis selgelt ei olnud, et näiteks -
meil on midagi tagastada,
ja me läheme tagasi -1.
Ja me lihtsalt tagasi -1 sest see positsioon
et ei ole olemas massiiv.
Ja nii see tähendab, et kui sa saad selle tagasi funktsioon
ta ütleb: "Hmm, okei. vist ei leidnud ma midagi.
Nii et 500 kunagi oli seal. "
Tore asi lineaarne otsing on see, et
see saab töötada mis tahes elementide loetelu,
olenemata sellest, kuidas esemed on tellitud.
See ei ole tähtis, kus brokoli on toota vahekäiku.
Niikaua kui te jalutada mööda vahekäiku algusest lõpuni,
sa oled kindlasti leida see,
eeldades poest ei ole otsa brokkoli, muidugi.
Aga see suurimaks tugevuseks on ka see suurim nõrkus.
Oletame, et teil on nimekiri 200 numbrid
et on järjestatud 1-200.
Kui otsite nr 198,
teil on otsida peaaegu kogu nimekiri numbrid
enne leida üks otsite.
Peab olema parem moodus!
Võite kindel olla, et on.
Aga see on teema teise video.
Samuti ärge vihastama!
Lihtsalt, sest lineaarne otsing ei ole parim lahendus igas olukorras,
see ei tähenda, et see ei tule käepärane.
Muidu, kuidas te leiate, et brokkoli on toota vahekäiku?
Minu nimi on Patrick Schmid, ja see on CS50.
[CS50.TV]