Vysvetlené algoritmy lineárneho a binárneho vyhľadávania

Schopnosť vyhľadávať niektoré údaje je dôležitým aspektom informatiky. Na vyhľadanie konkrétnej položky v množine údajov sa používajú vyhľadávacie algoritmy.

Algoritmy vracajú do vyhľadávacieho dopytu logický výsledok (pravdivý alebo nepravdivý). Môžu byť tiež upravené tak, aby poskytovali relatívnu polohu nájdenej hodnoty.

V tomto článku sa algoritmy zamerajú na určenie, či hodnota existuje.

Algoritmy lineárneho vyhľadávania

Lineárne vyhľadávanie je známe aj ako sekvenčné vyhľadávanie. Pri tomto type vyhľadávania sa každá hodnota v zozname navštevuje jedna po druhej usporiadaným spôsobom a kontroluje sa, či požadovaná hodnota existuje.

Algoritmus kontroluje hodnotu podľa hodnoty, kým nenájde hodnotu, ktorú hľadáte, alebo sa mu vyčerpajú hodnoty na vyhľadávanie. Keď sa mu začnú míňať hodnoty, znamená to, že váš vyhľadávací dopyt v zozname neexistuje.

Algoritmus sekvenčného vyhľadávania berie ako svoje parametre zoznam hodnôt a požadovanú položku v zozname. Návratový výsledok je inicializovaný ako Falošné a zmení sa na Pravda keď sa nájde požadovaná hodnota.

Ako príklad si pozrite nižšie uvedenú implementáciu Pythonu:

def linearSearch (mylist, item):

nájdené = nepravdivé

index = 0

zatiaľ čo index

if mylist [index] == položka:

nájdené = pravda

inak:

index = index+1

nájdený návrat

Analýza algoritmu

Najlepší scenár nastane, keď je požadovaná položka na prvom mieste v zozname. Najhorší prípad nastane, keď je požadovaná položka posledná v zozname (n. Položka). Časová náročnosť lineárneho vyhľadávania je preto O (n).

Priemerný scenár prípadu vo vyššie uvedenom algoritme je n/2.

Súvisiace: Čo je to Big-O notácia?

Upravené lineárne vyhľadávanie

Je dôležité vedieť, že použitý algoritmus predpokladá, že mu je poskytnutý náhodný zoznam položiek. To znamená, že položky zoznamu nie sú v konkrétnom poradí.

Predpokladajme, že položky boli v určitom poradí, povedzme od najmenších po najväčšie. Pri výpočte by bolo možné dosiahnuť určitú výhodu.

Zoberme si príklad hľadania 19 v danom zozname: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Po dosiahnutí 23 rokov bude zrejmé, že hľadaná položka v zozname neexistuje. Preto už nebude dôležité pokračovať vo vyhľadávaní zvyšných položiek zoznamu.

Algoritmy binárneho vyhľadávania

Videli ste, ako môže usporiadaný zoznam znížiť potrebný výpočet. Algoritmus binárneho vyhľadávania využíva ešte väčšiu výhodu z tejto účinnosti, ktorú prináša usporiadaný zoznam.

Algoritmus začína tak, že vezme strednú hodnotu usporiadaného zoznamu a skontroluje, či je to požadovaná hodnota. Ak nie je, potom sa skontroluje hodnota, či je menšia alebo väčšia ako požadovaná hodnota.

Ak je to menej, potom nie je potrebné kontrolovať spodnú polovicu zoznamu. V opačnom prípade, ak je väčší, presunie sa do hornej polovice zoznamu.

Súvisiace: Čo je to rekurzia a ako ju používate?

Bez ohľadu na to, ktorý sublist (ľavý alebo pravý) je zvolený, bude opäť stanovená stredná hodnota. Hodnota sa znova skontroluje, ak je to požadovaná hodnota. Ak nie je, skontroluje sa, či je menšia alebo väčšia ako požadovaná hodnota.

Tento proces sa opakuje, kým sa nenájde hodnota, ak tam je.

Nasledujúca implementácia Pythonu je pre algoritmus binárneho vyhľadávania.

def binarySearch (mylist, item):

nízka = 0

high = len (mylist) - 1

nájdené = nepravdivé

zatiaľ čo nízky <= vysoký a nebol nájdený:

stred = (nízky + vysoký) // 2

if mylist [mid] == item:

nájdené = pravda

elif item

vysoká = stredná - 1

inak:

nízka = stredná + 1

nájdený návrat

Analýza algoritmu

Najlepší scenár nastane, keď sa zistí, že požadovaná položka je strednou položkou. Najhorší scenár však nie je taký jednoduchý. Postupujte podľa nižšie uvedenej analýzy:

Po prvom porovnaní zostane n/2 položiek. Po druhom zostane n/4 položiek. Po tretej, n/8.

Všimnite si, že počet položiek sa stále znižuje na polovicu, kým nedosiahne n/2i, kde i je počet porovnaní. Po všetkom rozdelení skončíme iba s 1 položkou.

To znamená:

n/2i = 1

Binárne vyhľadávanie je preto O (log n).

Prechod na triedenie

Pri binárnom vyhľadávaní sme zvažovali prípad, keď už bolo dané pole zoradené. Predpokladajme však, že ste mali neusporiadaný súbor údajov a chceli ste v ňom vykonať binárne vyhľadávanie. Čo by si robil?

Odpoveď je jednoduchá: zoraďte to. V informatike existuje množstvo triediacich techník, ktoré boli dobre preskúmané. Jednou z týchto techník, ktoré môžete začať študovať, je algoritmus triedenia výberu, zatiaľ čo máme veľa sprievodcov týkajúcich sa aj iných oblastí.

Ako používať triedenie výberu

Zoradenie výberu je pre začiatočníkov trochu zložité, ale nie je to príliš náročné, keď sa vo veciach zorientujete.

Čítajte ďalej

O autorovi