[Powered by Google Translate] [Linear iskanje]
[Patrick Schmid, Harvard University]
[To je CS50.] [CS50.TV]
Iskanje je nekaj, kar ste verjetno bolj pogosto, kot si mislite.
Očitno je, da vsakič, ko odpre spletni brskalnik
in iskanje spletne strani -
ali iskanje za svoje prijatelje na vaš najljubši socialne mreže na mestu -
iščete.
Ampak to je samo majhen del iskanja, ki vam na dnevni osnovi.
Če želite, da bi našli, da je ena modro srajco v omari,
ali da je popolna rdeča bluza za to priložnost,
iščete.
Ko greste v trgovino, da še nikoli niste bili na prej,
in iščete brokoli proizvajajo v hodniku
iščete.
Kaj ste morda začeli opažati
je to odvisno od tega, kaj iščete
ali kako predmeti so organizirani, ko ste iskali za njih
učinkujejo na način, kako iskati.
Na primer, če vaše srajce visijo v omari,
lahko verjetno samo izločiti, ne da bi veliko iskanja.
Če ste ob predpostavki, da imate na sprehod do oltarja
da bi dobili brokoli, boste verjetno morali pogledati vse druge zelenjave
preden boste ugotovili, da brokoli.
Linearni Iskanje je primer take metode Iskanje - ali algoritem.
Kot pove že ime,
Ta metoda poišče element v linearno, eden za drugim.
Torej, če ste iskali na rezultate iz vašega priljubljenega iskalnika
in ste prebrali določitvi seznama rezultatov,
uporabljate linearno iskanje.
Ok. Oglejmo si primer.
Pravijo, da imamo seznam številk - 2, 4, 0, 5, 3, 7, 8 in 1 -
in iščemo za številko 0.
Očitno je, da lahko samo videli, da je 0 na tretjem mestu.
Ampak, računalniški program, ki ni srečen.
To je lahko samo "videti" eno številko naenkrat.
Torej, z začetkom na začetku seznama,
le "vidi" je 2.
Program nato preveri - je 2 enak 0?
Očitno ne. Torej, gre na naslednjo številko, 4.
Ali 4 enake 0? Ne.
Naslednji 1, 0. Ah! Zero je enak 0.
Tam smo ga imeli! To je v tretjem mestu.
Ok. Oglejmo si nekaj psevdokod.
To je samo nekaj vrstic, vendar pa si poglejmo na to eno vrstico naenkrat.
Prvič, kaj je opredeliti vlogo - in bomo rekli linearno iskanje -
in to traja dva argumenta - ključ in paleto.
Ključno je, da se vrednost, ki jo iščemo,
Tako v prejšnjem primeru, da je bila enaka nič.
Matrika je seznam številk
ki ima vse vrednosti, ki jih bomo iskali.
Torej, kaj želimo storiti, je, da smo želeli videti na -
iz vseh položajev, tako da se začne na samem začetku niza
til samega konca niza - tako na dolžino niza -
pogled na vsako mesto in preverite vsako posebej.
Torej, to je tisto, da je "za" zanka počne.
In v vsakem položaju, bomo rekli
"Ali je ta vrednost v tej trenutni položaj, ki je enak ključu, ki ga iščete?"
Torej - v prejšnjem primeru še enkrat, ključ je bil 0 -
zato smo rekli: "Je matrika na položaju i enaka nič?"
Če je tako, bomo vrnili "i", ker to je trenutni položaj smo na.
Torej, v prejšnjem primeru,
da je tretje mesto.
Če smo šli skozi celoten niz
in nismo našli ničesar -
Tako recimo smo iskali številko 500
ki očitno ni bil v tem primeru -
bomo morali vrniti nekaj,
in bomo -1 vrniti.
In mi smo pravkar vrnil -1, ker je to stališče
ki ne obstaja v polje.
In tako to pomeni, da ko si jo dobil nazaj od funkcije
pravi: "Hm, okej. Mislim, da niso našli ničesar.
Tako, da 500 ni bilo nikoli tam. "
Za lepo stvar je, da se linearno iskanje
da bo delovalo na nobenem seznamu predmetov,
ne glede na to, kako se naročiti postavke.
Ni važno, če je brokoli je v proizvajajo oltarja.
Dokler boste sprehod do oltarja od začetka do konca,
ste dolžni najti,
ob predpostavki, da trgovina ni zmanjkalo brokoli, seveda.
Ampak to je največja moč je tudi, da je največja slabost.
Recimo, da imate seznam 200 številk
, ki so razporejene 1-200.
Če iščete za številko 198,
boste morali iskati skoraj celoten seznam številk
preden boste našli enega, ki ga iščete.
Mora biti boljši način!
Bodite prepričani, da je.
Ampak to je tema za drug video.
Prav, ne skrbi!
Samo zato, ker linearni iskanje ni najboljša rešitev v vseh situacijah,
to ne pomeni, da ne pride v poštev.
V nasprotnem primeru, kako bi našli, da je brokoli v hodniku proizvajajo?
Moje ime je Patrick Schmid, in to je CS50.
[CS50.TV]