Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linear Szukaj]
[Patrick Schmid, Harvard University]
[To jest CS50.] [CS50.TV]
Masz coś, co prawdopodobnie zrobić częściej niż myślisz.
Oczywiście, za każdym razem otworzyć przeglądarkę internetową
i szukaj na stronie internetowej -
lub wyszukaj znajomymi na ulubionym portalu społecznościowego -
szukasz.
Ale to tylko niewielka część poszukiwań, co robisz na co dzień.
Gdy chcesz znaleźć tę jedną niebieską koszulę w szafie,
lub czerwone bluzki idealne na tę okazję
szukacie.
Gdy idziesz do sklepu, że nigdy nie byli w przed,
i szukasz brokułów w nawie spożywczego
szukacie.
Co może zaczęli dostrzegać
jest to, że w zależności od tego, czego szukasz
lub w jaki sposób elementy są organizowane, gdy szukasz dla nich
ma wpływ na sposób wyszukiwania.
Na przykład, jeśli twoje koszule wiszą w szafie,
prawdopodobnie można po prostu wybrać to bez wielu poszukiwaniach.
Jeśli zakładając, że masz iść do ołtarza
dostać brokuły, prawdopodobnie masz patrzeć na wszystkich innych warzyw
zanim znajdziesz tego brokuły.
Linear Search jest przykładem takiego sposobu Wyszukiwanie - lub algorytm.
Jak sama nazwa wskazuje,
Sposób ten wyszukuje elementu w sposób liniowy, jedna po drugiej.
Tak więc, gdy patrzysz na wynikach ulubionej wyszukiwarce
i czytać w dół listy wyników,
używasz liniowego wyszukiwania.
Okay. Spójrzmy na przykład.
Powiedzieć, że mamy listę liczb - 2, 4, 0, 5, 3, 7, 8 i 1 -
i szukamy dla 0 liczb.
Oczywiście, można po prostu zobaczyć, że 0 jest na trzeciej pozycji.
Ale program komputerowy nie jest szczęśliwy.
Może tylko "zobaczyć" jeden numer na raz.
Tak więc, w tym począwszy od początku na liście
tylko "widzi" 2.
Program sprawdza - jest 2 równe 0?
Oczywiście, że nie. Tak dalej do następnego numeru, 4.
Czy 4 równe 0? Nope.
Następny, 0. Ah! Zero jest równa 0.
Nie mamy go! Jest w trzeciej pozycji.
Okay. Spójrzmy na niektóre Pseudokod.
To tylko kilka linijek, ale spójrzmy na to jeden wiersz na raz.
Najpierw zdefiniujmy funkcję - i będziemy nazywać liniowym search -
i trwa dwa argumenty - klucz i tablicę.
Kluczem jest to, że wartość, którą szukasz,
tak, w poprzednim przykładzie, że był zerowy.
Tablica jest lista numerów
który ma wszystkie wartości, które mamy zamiar szukać.
Tak, to, co chcemy zrobić, to chcemy patrzeć -
wszystkich stanowiskach, więc już na początku tablicy
aż do samego końca tablicy - tak długości tablicy -
spojrzeć na każdym stanowisku i sprawdzić każdy z nich.
Więc to, że "dla" loop robi.
I w każdej pozycji, będziemy mówić
"Czy to jest napięcie w tym aktualnej pozycji równej klucz szukamy?"
SO - w poprzednim przykładzie znowu klucz był 0 -
więc mówią: "Czy tablica w pozycji i równa zero?"
Jeśli tak, to mamy zamiar wrócić "ja", ponieważ jest to aktualna pozycja jesteśmy na.
Tak więc, w powyższym przykładzie,
to była trzecia pozycja.
Jeśli przeszłam całej tablicy
i nie znalazłem nic -
więc powiedzmy szukaliśmy numeru 500
który oczywiście nie był w tym przykładzie -
musimy wrócić coś
i zamierzamy wrócić -1.
A my po prostu przekazujących -1 bo to stanowisko
, który nie istnieje w tablicy.
A więc to oznacza, kiedy się go z funkcji
mówi "Hmm, w porządku. Chyba nie znaleźliśmy niczego.
Tak, że nigdy 500 było. "
Ciekawą rzeczą jest to, że wyszukiwanie liniowej
będziesz pracować na żadnej liście przedmiotów,
niezależnie od tego, w jaki sposób elementy są uporządkowane.
To nie ma znaczenia, gdzie brokuły jest w przejściu produkcji.
Tak długo, jak iść do ołtarza, od początku do końca,
jesteś zobowiązany go znaleźć,
zakładając, że sklep nie zabrakło brokuły, oczywiście.
Ale to jest największym atutem jest także to największa słabość.
Powiedzmy, że masz listę dwustu numerów
które są oddzielone od 1 do 200.
Jeśli szukasz dla numeru 198,
trzeba szukać prawie całą listę numerów
zanim znajdziesz ten, którego szukasz.
Musi być lepszy sposób!
Bądźcie pewni, że jest.
Ale to temat na inny film.
Również, nie denerwować!
Tylko dlatego, że liniowy wyszukiwarka nie jest najlepszym rozwiązaniem w każdej sytuacji jest
to nie znaczy, że nie ma się przydać.
W przeciwnym razie, jak można stwierdzić, że brokuły w nawie produkować?
Nazywam się Patrick Schmid, a to CS50.
[CS50.TV]