Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linear търсене]
[Патрик Шмид, Харвардския университет]
[Това е CS50. [CS50.TV]
Търсене е нещо, което най-вероятно по-често, отколкото си мислите.
Очевидно е, че всеки път, когато отворите уеб браузър
и търсене на дадена уеб страница -
или търсене на вашите приятели в любимия си сайт за социални контакти -
търсите.
Но това е само една малка част от търсенията, което правите на дневна база.
Когато искате да откриете, че една синя риза в гардероба,
или че перфектно червена блуза за случая,
, което търсите.
Когато отидете до магазина, че никога не сте били преди,
и търсите за броколи в продукцията пътеката
, което търсите.
Какво може да са започнали да забележите
е, че в зависимост от това, което търсите
или как са организирани, когато търсите за тях
има ефект за това как да търсите.
Например, ако са окачени в гардероба си ризи,
вероятно можете да го вземете без много търсене.
Ако сте се предположи, че трябва да ходят по пътеката
за да получите броколи, най-вероятно трябва да разгледаме всички други зеленчуци
преди да установите, че броколи.
Linear търсене е пример за един такъв метод за търсене или алгоритъм.
Както подсказва името,
този метод търси за един артикул в линейна прогресия, един след друг.
Така че, когато търсите в резултатите от любимата си търсачка
и можете да прочетете списъка с резултати,
използвате линейна търсене.
Добре. Нека разгледаме един пример.
Кажем, че имаме списък с числа - 2, 4, 0, 5, 3, 7, 8, 1 -
и ние не търсим за броя 0.
Очевидно е, че може просто да се види, че 0 е на трета позиция.
Но, една компютърна програма не е късмет.
Той може само да "виждат" един номер в даден момент.
Така че, като се започне в началото на списъка,
само "вижда" 2.
Програмата проверява - 2 равна на 0?
Очевидно не. Така той отива към следващата цифра, 4.
Ли четири равни 0? Не.
Следващия, 0. Ах! Нулата е равен на 0.
Там ние я имаме! Това е на трета позиция.
Добре. Нека разгледаме някои pseudocode.
Това е само няколко дълги линии, но нека да разгледаме един ред наведнъж.
Първо, нека да определят функцията - и ние ще го наричат линейно търсене -
и отнема два аргумента - ключ и масив.
Важното е, че стойността, която ние търсим,
така и в предишния пример, че е нула.
Масивът е списък на телефонните номера
, който разполага с всички ценности, които ние започваш да търсите.
Така че, това, което искаме да направим е, че ние искаме да разгледаме
от всички позиции, така че в самото начало на масива
Тил самия край на масива - така че дължината на масива -
разгледаме всяка една позиция и провери всяка от тях.
Така че какво е това "за" примка прави.
И всяка позиция, започваш да се каже
- Тази стойност, че настоящата позиция, равна на ключа, който търсим?
Така че - отново в предишния пример, ключ е 0 -
затова ние казваме "масив в позиция равна на нула?
Ако това е така, ние ще се върне "аз", защото това е текущата позиция, ние сме в.
Така че, в предишния пример,
че е на трета позиция.
Ако сме преминали през целия масив
и не сме намерили нищо -
така че нека да кажем, че търсим номер 500
, която явно не е в този пример -
ние трябва да върнем нещо,
и отиваме да се върне -1.
И ние просто се връщат -1, защото това е състояние
, което не съществува в масива.
И така, това означава, че когато се върна от функция
той казва: "Хм, добре, предполагам, че не намери нищо.
Така че никога не 500 беше там. "
Хубавото за линеен търсене е, че
, че ще работи в някой списък на елементите,
независимо от начина, по който са подредени.
Няма значение къде броколите е в производство пътеката.
Тъй като ходиш по пътеката от началото до края,
вие сте длъжни да го намерите,
поемането на магазина не е свършила броколи, разбира се.
Но това е най-голямото предимство е, че е най-голямата слабост.
Кажем, че имате списък от двеста номера
, които са подредени 1-200.
Ако търсите за номер 198,
трябва да се търси почти целия списък от числа
, преди да намерите този, който търсите.
Трябва да има по-добър начин!
Уверяваме Ви, че има.
Но това е тема за друг видеоклип.
Също така, не гриза!
Само защото линейно търсене не е най-доброто решение във всички ситуации,
това не означава, че тя не дойде по-удобно.
В противен случай, как ще установите, че броколи в продукцията пътеката?
Моето име е Патрик Шмид, и това е CS50.
[CS50.TV]