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

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

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





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



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





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

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

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



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

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



def linearSearch(mylist, item):
found = False
index = 0
while index if mylist[index] == item:
found = True
else:
index = index+1
return found

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

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

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



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

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

как да изключите ps4 с контролер

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

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

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

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

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

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

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

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

защо firefox е толкова бавен?

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

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

def binarySearch (mylist, item):

low = 0
high = len(mylist) - 1
found = False
while low <= high and not found: mid = (low + high) // 2
if mylist[mid] == item:found = True
elif item else:low = mid + 1
return found

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

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

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

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

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

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

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

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

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

Дял Дял Туит електронна поща Как да използвате сортиране за избор

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

Прочетете Напред Свързани теми
  • Програмиране
  • Обяснена технология
  • Програмиране
  • Алгоритми
  • Анализ на данни
За автора Джером Дейвидсън(22 статии са публикувани)

Джером е щатен писател в MakeUseOf. Той обхваща статии за програмиране и Linux. Той също е ентусиаст на крипто и винаги следи крипто индустрията.

Още от Джером Дейвидсън

Абонирайте се за нашия бюлетин

Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и изключителни оферти!

Щракнете тук, за да се абонирате