Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineární vyhledávání]
[Patrick Schmid, Harvard University]
[This Is CS50.] [CS50.TV]
Vyhledávání je něco, co asi dělat častěji, než si myslíte.
Je zřejmé, že pokaždé, když otevřete webový prohlížeč
a hledání webové stránky -
nebo hledání přátel na své oblíbené sociální sítě -
hledáte.
Ale to je jen malá část vyhledávání, které budete dělat na denní bázi.
Pokud chcete zjistit, že jeden modrou košili ve skříni,
nebo že ideální červená halenka pro tuto příležitost,
hledáte.
Když jdete do obchodu, že jste nikdy nebyl předtím,
a hledáte pro brokolice v potravinářský uličce
hledáte.
Co jste možná začali všímat
je, že v závislosti na tom, co hledáte
nebo jak položky jsou uspořádány když hledáte pro ně
to má vliv na to, jak budete vyhledávat.
Například, pokud vaše košile visí ve skříni,
můžete asi jen vybrat to bez většího hledání.
Pokud jste za předpokladu, že budete muset chodit uličkou
dostat brokolici, budete pravděpodobně muset podívat na všechny ostatní zeleniny
před zjistíte, že brokolice.
Lineární vyhledávání je příklad jednoho takového prohledávání metody - nebo algoritmus.
Jak název napovídá,
Tato metoda vyhledá položky v lineárně, jedna po druhé.
Takže, když se díváte na výsledky z vašeho oblíbeného vyhledávače
a budete číst se stanoví seznam výsledků,
používáte lineární hledání.
Dobře. Pojďme se podívat na příklad.
Řekněme, že máme seznam čísel - 2, 4, 0, 5, 3, 7, 8, a 1 -
a hledáme pro číslo 0.
Je zřejmé, že stačí vidět, že 0 je na třetím místě.
Ale, počítačový program, není to štěstí.
To může jen "vidět" jedno číslo po druhém.
Takže, od počátku seznamu,
pouze "vidí" 2.
Program pak kontroluje - je 2 rovna 0?
Samozřejmě, že ne. Tak to pokračuje na další číslo, 4.
Má 4 rovné 0? Ne.
Ten příští, 0. Ah! Nula je rovna 0.
Tady to máme! Je to na třetí pozici.
Dobře. Pojďme se podívat na nějaké pseudokódu.
Je to jen pár řádků dlouhých, ale pojďme se podívat na to jeden řádek najednou.
Za prvé, pojďme definovat funkci - a budeme to nazývat lineární hledání -
a to trvá dva argumenty - klíč a pole.
Klíčem je, že hodnota, která jsme hledali,
takže v předchozím příkladu, že je nulová.
Pole je seznam čísel
, který má všechny hodnoty, které budeme hledat.
Takže, co chceme udělat, je chceme se podívat na -
ze všech pozic, takže začíná na samém začátku pole
až do úplného konce pole - takže délka pole -
podívejte se na každé místo a zkontrolujte, každý z nich.
Takže to je to, co to "pro" smyčky dělá.
A v každé poloze, budeme říkat
"Je to hodnota na aktuální pozici, která se rovná klíč, který jsme hledali?"
Takže - v předchozím příkladu znovu, klíč byl 0 -
tak říkáme "Je pole na pozici i rovná nule?"
Pokud je, budeme se vrá*** 'i', protože to je aktuální pozice jsme.
Takže, v předchozím příkladu,
to bylo třetí místo.
Pokud jsme prošli celé pole
a my jsme nenašli nic -
takže řekněme, že hledali číslo 500
který jasně nebyl v tomto příkladu -
musíme se vrá*** něco,
a budeme vrátí -1.
A my jsme jen vrací -1, protože to je pozice
že neexistuje v poli.
A tak to znamená, že když dostanete zpět z funkce
říká, že "Hmm, dobře. Myslím, že jsem nenašel nic.
Takže 500 nikdy tam byl. "
Pěkná věc, o lineární hledání je, že
že to bude fungovat na jakémkoliv seznamu položek,
bez ohledu na to, jak jsou seřazeny položky.
Nezáleží na tom, kde je, že brokolice je v potravinářský uličce.
Tak dlouho, jak budete chodit uličkou od začátku až do konce,
jste povinni najít,
za předpokladu, že obchod nebyl spuštěn z brokolice, samozřejmě.
Ale je to největší síla je také to je největší slabina.
Řekněme, že máte seznam 200 čísel
, které jsou seřazeny 1-200.
Pokud hledáte pro počet 198,
budete muset hledat téměř celý seznam čísel
než najdete ten, který hledáte.
Musí existovat lepší způsob!
Ujišťujeme vás, tam je.
Ale to je téma na jiný video.
Také, netrapte se!
Jen proto, že lineární hledání není nejlepší řešení ve všech situacích,
to neznamená, že to nepřijde vhod.
V opačném případě, jak by vás, že brokolice v potravinářský uličky?
Mé jméno je Patrick Schmid, a to je CS50.
[CS50.TV]