Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineárne vyhľadávanie]
[Patrick Schmid, Harvard University]
[This Is CS50.] [CS50.TV]
Vyhľadávanie je niečo, čo asi robiť častejšie, než si myslíte.
Je zrejmé, že zakaždým, keď otvoríte webový prehliadač
a hľadanie webové stránky -
alebo hľadanie priateľov na svoje obľúbené sociálne siete -
hľadáte.
Ale to je len malá časť vyhľadávanie, ktoré budete robiť na dennej báze.
Ak chcete zistiť, že jeden modrú košeľu v skrini,
alebo že ideálne červená blúzka pre túto príležitosť,
hľadáte.
Keď idete do obchodu, že ste nikdy nebol predtým,
a hľadáte pre brokolica v potravinársky uličke
hľadáte.
Čo ste možno začali všímať
je, že v závislosti na tom, čo hľadáte
alebo ako položky sú usporiadané keď hľadáte pre ne
to má vplyv na to, ako budete vyhľadávať.
Napríklad, ak vaše košele visia v skrini,
môžete asi len vybrať to bez väčšieho hľadanie.
Ak ste za predpokladu, že budete musieť chodiť uličkou
dostať brokolicu, budete pravdepodobne musieť pozrieť na všetky ostatné zeleniny
pred zistíte, že brokolica.
Lineárne vyhľadávanie je príklad jedného takého prehľadávanie metódy - alebo algoritmus.
Ako názov napovedá,
Táto metóda vyhľadá položky v lineárne, jedna po druhej.
Takže, keď sa pozeráte na výsledky z vášho obľúbeného vyhľadávača
a budete čítať sa ustanovuje zoznam výsledkov,
používate lineárne hľadanie.
Dobre. Poďme sa pozrieť na príklad.
Povedzme, že máme zoznam čísel - 2, 4, 0, 5, 3, 7, 8, a 1 -
a hľadáme pre číslo 0.
Je zrejmé, že stačí vidieť, že 0 je na treťom mieste.
Ale, počítačový program, nie je to šťastie.
To môže len "vidieť" jedno číslo po druhom.
Takže, od začiatku zoznamu,
len "vidí" 2.
Program potom kontroluje - je 2 rovná 0?
Samozrejme, že nie. Tak to pokračuje na ďalšie číslo, 4.
Má 4 rovné 0? Nie.
Budúci, 0. Ah! Nula je rovná 0.
Tu to máme! Je to na tretiu pozíciu.
Dobre. Poďme sa pozrieť na nejaké pseudokódu.
Je to len pár riadkov dlhých, ale poďme sa pozrieť na to jeden riadok naraz.
Po prvé, poďme definovať funkciu - a budeme to nazývať lineárne hľadanie -
a to trvá dva argumenty - kľúč a polia.
Kľúčom k úspechu je, že hodnota, ktorá sme hľadali,
takže v predchádzajúcom príklade, že je nulová.
Pole je zoznam čísel
, Ktorý má všetky hodnoty, ktoré budeme hľadať.
Takže, čo chceme urobiť, je chceme sa pozrieť na -
zo všetkých pozícií, takže začína na samom začiatku poľa
až do úplného konca poľa - takže dĺžka poľa -
pozrite sa na každé miesto a skontrolujte, každý z nich.
Takže to je to, čo to "pre" slučky robí.
A v každej polohe, budeme hovoriť
"Je to hodnota na aktuálnu pozíciu, ktorá sa rovná kľúč, ktorý sme hľadali?"
Takže - v predchádzajúcom príklade znova, kľúč bol 0 -
tak hovoríme "Je poľa na pozícii i rovná nule?"
Ak je, budeme sa vrátiť 'i', pretože to je aktuálna pozícia sme.
Takže, v predchádzajúcom príklade,
to bolo tretie miesto.
Ak sme prešli celé pole
a my sme nenašli nič -
takže povedzme, že hľadali číslo 500
ktorý jasne nebol v tomto príklade -
musíme sa vrátiť niečo,
a budeme vráti -1.
A my sme len vracia -1, pretože to je pozícia
že neexistuje v poli.
A tak to znamená, že keď dostanete späť z funkcie
hovorí, že "Hmm, dobre. Myslím, že som nenašiel nič.
Takže 500 nikdy tam bol. "
Pekná vec, o lineárny hľadanie je, že
že to bude fungovať na akomkoľvek zoznamu položiek,
bez ohľadu na to, ako sú zoradené položky.
Nezáleží na tom, kde je, že brokolica je v potravinársky uličke.
Tak dlho, ako budete chodiť uličkou od začiatku až do konca,
ste povinní nájsť,
za predpokladu, že obchod nebol spustený z brokolice, samozrejme.
Ale je to najväčšia sila je tiež to je najväčší slabina.
Povedzme, že máte zoznam 200 čísel
, Ktoré sú zoradené 1-200.
Ak hľadáte pre počet 198,
budete musieť hľadať takmer celý zoznam čísel
ako nájdete ten, ktorý hľadáte.
Musí existovať lepší spôsob!
Uisťujeme vás, tam je.
Ale to je téma na iný video.
Tiež, netrápte sa!
Len preto, že lineárny hľadanie nie je najlepšie riešenie vo všetkých situáciách,
to neznamená, že to nepríde vhod.
V opačnom prípade, ako by vás, že brokolica v potravinársky uličky?
Moje meno je Patrick Schmid, a to je CS50.
[CS50.TV]