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