[За възпроизвеждане на музика] Дъг LLOYD: Linear търсене е алгоритъм, ние можете да използвате, за да намерите елемент в масив. Един изземване алгоритъм е набор стъпка по стъпка на инструкции за попълването на дадена задача. 

Линейната търсенето алгоритъм работи по следния начин. Обхождане в масива от ляво на полето, грижа за определен елемент. 

В Псевдокод, което е по- дестилирана версия на това изречение, ако първият елемент е това, което което търсите, можете да се спрете. В противен случай, се премине към следващия елемент и продължавай отново и отново, докато не намерите елемента, или не. Така че ние можем да използваме линейния алгоритъм за търсене, например, да намерите целевата стойност девет в този масив. Ами ние започнем от самото начало. Ако това е, което ние сме търсите, можем да спрем. Той е не, ние не търсим 11. Така че в противен случай, преминете на следващия елемент. 

Така че ние гледаме на 23. Е 23, което ние, което търсите? Ами не, за да можем да преминем към следващия елемент, а на следващия елемент, и ние продължаваме да става чрез този процес отново и отново и отново, докато кацнем на ситуация като тази. 

Nine е това, което търсим, и този елемент на масива е, това е стойност е девет. И така ние открихме това, което сме търсите, и можем да спрем. Линейният търсачката има приключи успешно. 

Но какво да кажем, ако ние не търсим елемент, който не е в нашия масив. Дали линейно търсене все още работи? Ами сигурен. Така че ние се повтаря този процес като се започне от първия елемент. Ако това е, което ние сме търсите, можем да спрем. Не е. В противен случай, ние се премине към следващия елемент. 

Но ние можем да продължават да повтарят този процес, разглеждане на всеки елемент от своя страна, надявайки се, че ще открием броя 50. Но ние няма да знаем дали ние открихме броя 50 или ако не го направи, докато не стъпи над всеки един елемент от масива. 

Само веднъж сме направили че и излезе кратко, можем да заключим, че 50 не е в масива. И така линейния търсенето алгоритъм, и той не успя, само по себе си. Но не в смисъл, че не успява да прави това, което ние го помоли да направя. 

Той е бил неуспешен, както в колкото не беше намерен 50, 50, но не е в масива. Но ние сме изчерпателно търсене през всеки един елемент и така, докато ние не намери нещо, линейно търсене все още успява дори ако елемент, който не е в масива. 

Така че това, което е най-лошия случай сценарий с линейна търсене? Ами ние трябва да погледнем през всеки един елемент, или защото целевата елемент е последния елемент на масива, или елементът, който търсим не действително съществува в масива на всички. Какво е най-добрия случай? Ами ние може да откриете на елемент веднага. И колко много елементи ние след това трябва да погледнем на в най-добрия случай, ако ние не търсим за него и ние го намерите в самото начало? Можем да спрем веднага. 

Какво означава това за сложност на линейно търсене? Е, в най-лошия случай, ние имаме да разгледаме всеки един елемент. И така, той работи в O на N, в най-лошия случай. 

В най-добрия случай, ние ще намерите елемент веднага. И така спринта на омега на 1. 

Аз съм Дъг Лойд. Това е CS50.