[Powered by Google Translate] [Линеарна претрага]
[Патрицк Сцхмид, Универзитет Харвард]
[Тхис Ис ЦС50.] [ЦС50.ТВ]
Претраживање је нешто што вероватно не чешће него што мислите.
Очигледно, сваки пут када отворите веб прегледач
и потрага за веб страници -
или потрага за пријатељима на вашем омиљеном сајту за друштвено умрежавање -
тражите.
Али то је само мали део трагања који радите на дневној бази.
Када желите да пронађете ту једну плаву кошуљу у ормару,
или да савршено црвене блузе за ту прилику,
ви тражите.
Када одете у продавницу да никада нисам била од пре,
и ви сте у потрази за броколи на пијаци пролаз
ви тражите.
Оно што можда почели да примећују
је да, у зависности од тога шта сте тражили
или како се ствари су организовани када сте у потрази за њих
она има утицај на то како тражите.
На пример, ако ваше кошуље су виси у ормару,
вероватно да га само покупити без много тражи.
Ако сте под претпоставком да морају да пешаче до олтара
добити броколи, вероватно имате да погледате на свим другим поврћем
пре него што вам је тај броколи.
Линеарна претрага је пример једне такве методе у потрази - или алгоритму.
Као што назив имплицира,
овај метод трага за ставке у линеарном моду, једна иза друге.
Дакле, када гледамо резултате из вашег омиљеног претраживача
и ви прочитате доле листу резултата,
користите линеарну претрагу.
Ок. Погледајмо један пример.
Рецимо имамо списак бројева - 2, 4, 0, 5, 3, 7, 8, и 1 -
а ми тражимо број 0.
Очигледно, само се види да је 0 у трећем положају.
Али, компјутерски програм није толико среће.
То само може да "види" један број у једном тренутку.
Дакле, са почетком у почетку листе,
она само "види" 2.
Програм затим проверава - је 2 једнако 0?
Очигледно није. Тако то иде на следећи број, 4.
Да ли 4 једнаке 0? Јок.
Следећи један, 0. Ах! Нула је једнак 0.
Ту га имамо! То је у трећем месту.
Ок. Хајде да погледамо неке Псеудокод.
То је само пар линија дугих, али хајде да погледамо на то једну линију у исто време.
Прво, хајде да дефинишемо функцију - и ми ћемо га зову линеарна претрага -
и то траје два аргумента - тастер и низа.
Кључ је да вредност која тражимо,
тако да је у претходном примеру, то је био нула.
Низ је листа бројева
које има све вредности које смо ишли да претражите.
Дакле, оно што ми желимо да урадимо јесте желимо да погледамо -
из свих позиција, па почетком у самом почетку низа
тил самом крају низа - тако дужине низа -
погледати сваког положаја и проверите сваки од њих.
Дакле, то је оно што је "за" петља се ради.
И на свакој позицији, ми ћемо рећи
"Да ли је та вредност у тој тренутној позицији једнак тастеру да тражимо?"
Дакле - у претходном примеру, кључ је 0 -
тако да смо се говорећи: "Да ли је низ на позицији сам једнак нули?"
Ако јесте, ми ћемо вратити 'ја', јер је то тренутна позиција смо.
Дакле, у претходном примеру,
то је био трећи положај.
Ако смо прошли кроз цео низ
и нисмо нашли ништа -
па рецимо да смо у потрази за број 500
што јасно није био у том примеру -
морамо се вратити нешто,
и ми ћемо вратити -1.
А ми се враћамо -1 јер је то став
који не постоји у низу.
И то значи да када га добијете назад од функције
пише "Хм, ок. ваљда нисам нашао ништа.
Тако да 500 никада није био тамо. "
Лепа ствар у вези са линеарном претрази је да
да ће радити на било којој листи ставки,
без обзира како су ствари распоређене.
Није битно где се броколи је на пијаци пролазу.
Докле год хода низ пролаз од почетка до краја,
сте обавезни да га пронађе,
претпостављајући продавницу није понестало броколија, наравно.
Али то је највећа снага је такође то је највећа слабост.
Рецимо да имате листу двеста бројева
које су сортиране од 1 до 200.
Ако сте у потрази за број 198,
морате да претражите готово читаву листу бројева
пре него што пронађете ону коју тражите.
Мора постојати бољи начин!
Будите сигурни да има.
Али, то је тема за неки други видео.
Такође, не узрујавати!
Само зато што линеарно претраживање није најбоље решење у свим ситуацијама,
то не значи да то не долази у руци.
Иначе, како би вам тај броколи на пијаци пролаз?
Моје име је Патрик Шмит, а то је ЦС50.
[ЦС50.ТВ]