Vysvětleny lineární a binární vyhledávací algoritmy

Schopnost vyhledávat některá data je důležitým aspektem informatiky. K vyhledání konkrétní položky v sadě dat se používají vyhledávací algoritmy.

Algoritmy vracejí do vyhledávacího dotazu logický výsledek (true nebo false). Mohou být také upraveny tak, aby poskytovaly relativní polohu nalezené hodnoty.

V tomto článku se algoritmy soustředí na určení, zda hodnota existuje.

Algoritmy lineárního vyhledávání

Lineární vyhledávání je také známé jako sekvenční vyhledávání. V tomto typu vyhledávání je každá hodnota v seznamu navštívena jedna po druhé uspořádaným způsobem při kontrole, zda požadovaná hodnota existuje.

Algoritmus kontroluje hodnotu podle hodnoty, dokud nenajde hodnotu, kterou hledáte, nebo mu dojdou hodnoty pro hledání. Když mu dojdou hodnoty pro hledání, znamená to, že váš vyhledávací dotaz v seznamu neexistuje.

Algoritmus sekvenčního vyhledávání přebírá jako své parametry seznam hodnot a požadovanou položku v seznamu. Návratový výsledek je inicializován jako Nepravdivé a změní se na Skutečný když je nalezena požadovaná hodnota.

Podívejte se na příklad implementace Pythonu níže:

def linearSearch (mylist, item):

nalezeno = Nepravda

index = 0

while index

if mylist [index] == položka:

nalezeno = pravda

jiný:

index = index+1

nalezen návrat

Analýza algoritmů

Nejlepší scénář nastane, když je požadovaná položka první v seznamu. Nejhorší případ nastane, když je požadovaná položka poslední v seznamu (n. Položka). Časová složitost pro lineární vyhledávání je tedy O (n).

Průměrný scénář případu ve výše uvedeném algoritmu je n/2.

Příbuzný: Co je Big-O notace?

Upravené lineární vyhledávání

Je důležité vědět, že použitý algoritmus předpokládá, že je mu poskytnut náhodný seznam položek. To znamená, že položky seznamu nejsou v žádném konkrétním pořadí.

Předpokládejme, že položky byly v určitém pořadí, řekněme od nejmenšího po největší. Bylo by možné dosáhnout určité výhody ve výpočtu.

Vezměte si příklad hledání 19 v daném seznamu: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Po dosažení 23 let by bylo jasné, že hledaná položka v seznamu neexistuje. Proto by již nebylo důležité pokračovat ve vyhledávání ve zbývajících položkách seznamu.

Algoritmy binárního vyhledávání

Viděli jste, jak může seřazený seznam snížit potřebný výpočet. Algoritmus binárního vyhledávání využívá ještě více výhod této efektivity, kterou přináší seřazený seznam.

Algoritmus začíná tím, že vezme střední hodnotu uspořádaného seznamu a zkontroluje, zda je to požadovaná hodnota. Pokud tomu tak není, hodnota se zkontroluje, zda je menší nebo větší než požadovaná hodnota.

Pokud je to méně, pak není nutné kontrolovat spodní polovinu seznamu. V opačném případě, pokud je větší, přesune se do horní poloviny seznamu.

Příbuzný: Co je rekurze a jak ji používáte?

Bez ohledu na zvolený dílčí seznam (vlevo nebo vpravo) bude opět určena střední hodnota. Hodnota je znovu zkontrolována, pokud je to požadovaná hodnota. Pokud tomu tak není, kontroluje se, zda je menší nebo větší než požadovaná hodnota.

Tento proces se opakuje, dokud není nalezena hodnota, pokud tam je.

Níže uvedená implementace Pythonu je pro algoritmus binárního vyhledávání.

def binarySearch (mylist, item):

nízká = 0

high = len (mylist) - 1

nalezeno = Nepravda

zatímco nízká <= vysoká a nenalezena:

mid = (low + high) // 2

if mylist [mid] == item:

nalezeno = pravda

elif item

vysoká = střední - 1

jiný:

nízká = střední + 1

nalezen návrat

Analýza algoritmů

Nejlepší scénář nastane, když je požadovaná položka nalezena jako prostřední položka. Nejhorší scénář však není tak přímočarý. Postupujte podle níže uvedené analýzy:

Po prvním srovnání zbude n/2 položek. Po druhé zbude n/4 položek. Po třetí, n/8.

Všimněte si, že počet položek se stále snižuje na polovinu, dokud nedosáhne n/2i, kde i je počet srovnání. Po veškerém rozdělení skončíme pouze s 1 položkou.

Z toho vyplývá:

n/2i = 1

Binární vyhledávání je tedy O (log n).

Přechod na třídění

Při binárním vyhledávání jsme zvažovali případ, kdy již bylo dané pole objednáno. Předpokládejme však, že jste měli neuspořádanou datovou sadu a chtěli jste na ní provést binární vyhledávání. Co bys dělal?

Odpověď je jednoduchá: seřiďte to. V informatice existuje řada technik třídění, které byly dobře prozkoumány. Jednou z těchto technik, které můžete začít studovat, je algoritmus výběru, zatímco máme spoustu průvodců souvisejících i s jinými oblastmi.

Jak používat Selection Sort

Třídění výběru je pro začátečníky trochu složité na pochopení, ale není to příliš náročné, jakmile se zorientujete.

Číst dále

O autorovi