Vyhľadávanie je jedna z najčastejších operácií v informatike — hľadáme záznamy v databáze, súbory na disku alebo hodnoty v zozname. Výber správneho vyhľadávacieho algoritmu môže dramaticky ovplyvniť rýchlosť programu.
Lineárne vyhľadávanie
Lineárne vyhľadávanie (sequential search) prehľadáva prvky jeden po druhom od začiatku, kým nenájde hľadaný prvok alebo nedosiahne koniec.
def linearny_hladaj(zoznam, ciel):
for i in range(len(zoznam)):
if zoznam[i] == ciel:
return i # vráti index nájdeného prvku
return -1 # prvok nebol nájdený
cisla = [4, 7, 2, 9, 1, 5]
print(linearny_hladaj(cisla, 9)) # vypíše 3
Lineárne vyhľadávanie je jednoduché a funguje na akomkoľvek zozname — nemusí byť zoradený. Má však časovú zložitosť O(n): v najhoršom prípade musíme prejsť všetky prvky.
Lineárne vyhľadávanie je ideálne pre malé zoznamy alebo nezoradené dáta. Pre väčšie zoradené zoznamy existujú oveľa rýchlejšie alternatívy.
Binárne vyhľadávanie
Binárne vyhľadávanie funguje na zoradenom zozname. Princíp je podobný hľadaniu v slovníku: otvoríme stred, porovnáme hodnotu a ďalej hľadáme len v príslušnej polovici.
Hľadáme číslo 7 v zozname: [1, 3, 5, 7, 9, 11, 13]
Krok 1: stred = 7 (index 3). 7 == 7 → NÁJDENÉ!
Hľadáme číslo 11:
Krok 1: stred = 7. 11 > 7 → hľadáme v pravej časti [9, 11, 13]
Krok 2: stred = 11. 11 == 11 → NÁJDENÉ!
def binarny_hladaj(zoznam, ciel):
lavo, pravo = 0, len(zoznam) - 1
while lavo <= pravo:
stred = (lavo + pravo) // 2
if zoznam[stred] == ciel:
return stred
elif zoznam[stred] < ciel:
lavo = stred + 1
else:
pravo = stred - 1
return -1
Binárne vyhľadávanie má zložitosť O(log n) — pre milión prvkov stačí najviac 20 porovnaní.
Binárne vyhľadávanie funguje IBA na zoradenom zozname. Ak zoznam nie je zoradený, výsledok bude nesprávny. Pred použitím vždy skontrolujte, či sú dáta zoradené.
Kedy použiť ktorý algoritmus
| Situácia | Odporúčaný algoritmus |
|---|---|
| Malý zoznam (do ~20 prvkov) | Lineárne vyhľadávanie |
| Nezoradený zoznam | Lineárne vyhľadávanie |
| Veľký zoradený zoznam | Binárne vyhľadávanie |
| Opakované vyhľadávania v rovnakých dátach | Najprv zoriadiť, potom binárne |
Voľba algoritmu je kompromis medzi jednoduchosťou implementácie a výkonom. Pre väčšie aplikácie sa oplatí najprv dáta zoriadiť, aby sme mohli využiť binárne vyhľadávanie.
Cvičné príklady
Koľko porovnaní potrebuje binárne vyhľadávanie v najhoršom prípade pre zoradený zoznam s 128 prvkami?