Vyhľadávanie je jedna z najzákladnejších operácií v informatike. Lineárne vyhľadávanie je najjednoduchší spôsob — prechádza zoznam od začiatku do konca, kým nenájde hľadanú hodnotu.
Princíp
Algoritmus ide prvok po prvku:
- Pozri sa na prvý prvok. Je to ten, čo hľadáš?
- Ak áno — hotovo, vrát jeho polohu.
- Ak nie — prejdi na ďalší prvok.
- Ak si prešiel celý zoznam a nenašiel si — hodnota tam nie je.
Je to ako hľadať kľúče tak, že prehľadáváš každú vreckú po rade.
Implementácia v Pythone
def linearné_vyhľadávanie(zoznam, ciel):
for i in range(len(zoznam)):
if zoznam[i] == ciel:
return i # vrát index nájdeného prvku
return -1 # -1 znamená "nenašiel sa"
ovocie = ["jablko", "banán", "čerešňa", "hrozno", "kiwi"]
vysledok = linearné_vyhľadávanie(ovocie, "čerešňa")
print(vysledok) # 2
vysledok = linearné_vyhľadávanie(ovocie, "mango")
print(vysledok) # -1 (nenájdené)
Návratová hodnota -1 je bežná konvencia pre "nenájdené" v mnohých programovacích jazykoch. Môžeš tiež vrátiť None, čo je v Pythone prirodzenejšie.
Verzia s for-else
Python má špeciálnu konštrukciu for...else, kde else sa vykoná, ak cyklus prebehol bez break:
def hladaj(zoznam, ciel):
for i, prvok in enumerate(zoznam):
if prvok == ciel:
print(f"Nájdené na indexe {i}")
break
else:
print("Hodnota sa v zozname nenachádza")
hladaj([5, 3, 8, 1, 9], 8) # Nájdené na indexe 2
hladaj([5, 3, 8, 1, 9], 7) # Hodnota sa v zozname nenachádza
Vyhľadávanie v Pythone — operátor in
Python má vstavaný operátor in a metódu index():
cisla = [10, 20, 30, 40, 50]
print(30 in cisla) # True — je 30 v zozname?
print(cisla.index(30)) # 2 — na akom indexe je 30?
Tieto vstavané nástroje vnútorne používajú lineárne vyhľadávanie.
Analýza výkonu
| Prípad | Počet porovnaní | Situácia |
|---|---|---|
| Najlepší | 1 | Hľadaný prvok je na prvom mieste |
| Priemerný | N/2 | Prvok je niekde uprostred |
| Najhorší | N | Prvok je posledný alebo sa nenachádza |
Lineárne vyhľadávanie má časovú zložitosť O(N) — pri dvojnásobnom počte prvkov trvá dvakrát dlhšie. Pre malé zoznamy alebo jednorazové hľadanie je to v poriadku. Pre veľké dáta alebo časté vyhľadávanie existujú efektívnejšie riešenia.
Kedy použiť lineárne vyhľadávanie?
Lineárne vyhľadávanie je vhodné, keď:
- Zoznam je malý (do niekoľkých stoviek prvkov).
- Zoznam je nezoradený a nemáš čas ho triediť.
- Hľadáš raz — pre jediné hľadanie sa neoplatí triediť.
- Zoznam sa mení — udržiavanie zoradeného zoznamu by bolo nákladné.
Pre veľké, zoradené dáta je oveľa efektívnejšie binárne vyhľadávanie.
Ak hľadáš rovnaký prvok v rovnakom veľkom zozname mnohokrát, zvažuj zoriadenie zoznamu a použitie binárneho vyhľadávania, alebo uloženie dát do slovníka (dictionary) pre O(1) prístup.
Cvičné príklady
V akom najhoršom prípade musí lineárne vyhľadávanie preskontrolovať všetkých N prvkov zoznamu?
Zobraziť odpoveď
Uprav funkciu linearné_vyhľadávanie tak, aby vrátila zoznam VŠETKÝCH indexov, kde sa hľadaná hodnota nachádza (môže sa opakovať).