Обяснени линейни и двоични алгоритми за търсене

Възможността за търсене на някои данни е важен аспект на компютърните науки. Алгоритмите за търсене се използват за търсене на определен елемент в набор от данни.

Алгоритмите връщат логически резултат (вярно или невярно) в заявка за търсене. Те също могат да бъдат модифицирани, за да дадат относителната позиция на намерената стойност.

За тази статия алгоритмите ще се концентрират върху определянето дали съществува стойност.

Алгоритми за линейно търсене

Линейното търсене е известно още като последователно търсене. При този тип търсене всяка стойност в списък се посещава една по една по подреден начин, като същевременно се проверява дали желаната стойност съществува.

Алгоритъмът проверява стойността по стойност, докато намери стойността, която търсите, или свърши стойностите за търсене. Когато стойностите за търсене свършат, това означава, че заявката ви за търсене не съществува в списъка.

Алгоритъмът за последователно търсене приема списък със стойности и желания елемент от списъка като свои параметри. Резултатът за връщане се инициализира като

Фалшиво и ще се промени на Вярно когато се намери желаната стойност.

Вижте изпълнението на Python по -долу като пример:

def linearSearch (mylist, item):

намерено = невярно

индекс = 0

докато index

ако mylist [индекс] == елемент:

намерено = Вярно

иначе:

индекс = индекс+1

връщане намерено

Алгоритъмен анализ

Най-добрият сценарий се случва, когато желаният елемент е първият в списъка. Най -лошият случай се случва, когато желаният елемент е последният в списъка (n -тият елемент). Следователно времевата сложност за линейно търсене е O (n).

Средният сценарий в горния алгоритъм е n/2.

Свързани: Какво е Big-O нотация?

Модифицирано линейно търсене

Важно е да знаете, че използваният алгоритъм предполага, че му е предоставен случаен списък с елементи. Тоест елементите в списъка не са в определен ред.

Да предположим, че предметите са в определен ред, да речем от най -малкия до най -големия. Би било възможно да се постигне известно предимство при изчисленията.

Вземете пример за търсене на 19 в дадения списък: [2, 5, 6, 11, 15, 18, 23, 27, 34]. След като достигне 23, ще стане ясно, че търсеният елемент не съществува в списъка. Следователно вече няма да е важно да продължите да търсите останалите елементи от списъка.

Двоични алгоритми за търсене

Видяхте как подреден списък може да намали необходимото изчисление. Двоичният алгоритъм за търсене се възползва още повече от тази ефективност, отколкото наличието на подреден списък.

Алгоритъмът започва като взема средна стойност на подреден списък и проверява дали това е желаната стойност. Ако не е, тогава стойността се проверява дали е по -малка или по -голяма от желаната стойност.

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

Свързани: Какво е рекурсия и как я използвате?

Независимо кой подлист (ляв или десен) е избран, средната стойност отново ще бъде определена. Стойността отново се проверява дали е необходимата стойност. Ако не е, проверява се дали е по -малко или по -голямо от исканата стойност.

Този процес се повтаря, докато се намери стойност, ако е там.

Реализацията на Python по -долу е за алгоритъма за двоично търсене.

def binarySearch (mylist, item):

ниско = 0

високо = len (mylist) - 1

намерено = невярно

докато ниско <= високо и не е намерено:

mid = (ниско + високо) // 2

if mylist [mid] == item:

намерено = Вярно

elif item

висока = средна - 1

иначе:

ниска = средна + 1

връщане намерено

Алгоритъмен анализ

Най-добрият сценарий се случва, когато желаният елемент е средният елемент. Най-лошият сценарий обаче не е толкова ясен. Следвайте анализа по -долу:

След първото сравнение ще останат n/2 елемента. След второто ще останат n/4 елемента. След третия, n/8.

Забележете, че броят на елементите продължава да намалява наполовина, докато достигне n/2i, където i е броят на сравненията. След цялото разделяне получаваме само 1 елемент.

Това предполага:

n/2i = 1

Следователно, двоичното търсене е O (log n).

Преминаване към сортиране

При двоично търсене разгледахме случай, при който даденият масив вече е подреден. Но да предположим, че сте имали неуреден набор от данни и сте искали да извършите двоично търсене по него. Какво би направил?

Отговорът е прост: сортирайте го. Има редица техники за сортиране в компютърните науки, които са добре проучени. Една от тези техники, които можете да започнете да изучавате, е алгоритъмът за сортиране на подбора, докато имаме много ръководства, свързани и с други области.

Как да използвате Сортиране за избор

Подреждането на подбора е малко трудно за разбиране за начинаещи, но не е твърде предизвикателно, след като получите размах на нещата.

Прочетете Напред

За автора