[Гуляе музыка] Даг Lloyd: Лінейны Пошук алгарытм мы можна выкарыстоўваць для пошуку элемента ў масіве. Алгарытм водгук гэта крок за крокам набор інструкцый для выканання задачы. 

Лінейны пошук Алгарытм працуе наступным чынам. Ітэрацыі па масіву злева Права, гледзячы на ​​паказаным элеменце. 

У псевдокоде, які з'яўляецца больш дыстыляваная версія гэтай прапановы, Калі першы элемент што Вы шукаеце, вы можаце спыніцца. У адваротным выпадку, перайсці да наступнага элементу і працягваць зноў і зноў да таго часу, пакуль не знойдзеце элемент, ці вы не робіце. Такім чынам, мы можам выкарыстоўваць лінейную Алгарытм пошуку, напрыклад, знайсці мэтавае значэнне дзевяць у гэтым масіве. Ну, мы пачнем з самага пачатку. Калі гэта тое, што мы шукаеце, мы можам спыніць. Гэта не так, мы не шукаем 11. Так у адваротным выпадку, перайсці да наступнага элемента. 

Такім чынам, мы глядзім на 23. 23 тое, што мы шукаем? Ну не, так што мы пяройдзем да наступнага элемент, а наступны элемент, і мы працягваем перажывае Гэты працэс зноў і зноў, і больш, пакуль мы не прызямліцца па сітуацыі, як гэта. 

Дзевяць тое, што мы шукаем, і гэты элемент масіва ёсць, гэта значэнне складае дзевяць. І такім чынам, мы знайшлі тое, што мы шукаеце, і мы можам спыніцца. Лінейны пошук мае завершана паспяхова. 

Але што, калі мы шукаем элемент, які не ў масіве. Любая лінейны пошук ўсё яшчэ працуе? Ну вядома. Такім чынам, мы паўтараем гэты працэс пачынаючы з першага элемента. Калі гэта тое, што мы шукаеце, мы можам спыніць. Гэта не так. У адваротным выпадку, мы пераходзім да наступнага элемента. 

Але мы можам паўтараць гэты працэс, разглядаючы кожны элемент, у сваю чаргу, спадзеючыся, што мы знаходзім ліку 50. Але мы не будзеце ведаць, калі мы знайшлі нумар 50 або калі мы не зрабілі, пакуль мы не выйшаў над кожным аднаго элемента масіва. 

Толькі адзін раз мы зрабілі што і прыдумаць кароткі, мы можам зрабіць выснову, што 50 ня знаходзіцца ў масіве. І таму лінейны пошук Алгарытм, таксама ён не па сабе. Але не ў тым сэнсе, што гэта была няўдалай ў гэтым, што мы папрасілі яго зрабіць. 

Гэта было няўдалым, як колькі ён не знайшоў 50, але 50 не ў масіве. Але мы вычарпальна шукалі праз кожны асобны элемент і так, пакуль мы не знайшлі што-небудзь, лінейны пошук яшчэ паспяхова, нават калі элемент не ў масіве. 

Так што ў горшым выпадку Сцэнар з лінейным пошукам? Ну, мы павінны глядзець праз кожны элемент, альбо таму, што мэтавай элемент гэта апошні элемент масіва, або элемент, мы шукаем не на самай справе існуе ў масіве на ўсіх. Які самы лепшы сцэнар? Ну, мы маглі б знайсці элемент неадкладна. І колькі элементаў Такім чынам, мы павінны глядзець на, у лепшым выпадку, калі мы шукаем для яго і мы знаходзім яго ў самым пачатку? Мы можам спыніць неадкладна. 

Што гэта гаворыць аб Складанасць лінейнага пошуку? Ну ў горшым выпадку, у нас ёсць паглядзець на кожны асобны элемент. І так ён працуе ў O з N, у горшым выпадку. 

У лепшым выпадку, мы збіраемся адразу знайсці элемент. І так працуе амега 1. 

Я Дуг Лойд. Гэта CS50.