# Lineárne vyhľadávanie Vyhľadávanie je jednou z najčastejších operácií pri práci s dátami. Predstavte si, že máte zoznam položiek a potrebujete rýchlo zistiť, či sa v ňom nachádza konkrétna položka alebo kde presne je umiestnená. Pre tieto úlohy boli vyvinuté rôzne algoritmy. Jedným z najzákladnejších a najjednoduchších je **lineárne vyhľadávanie**. Lineárne vyhľadávanie je fundamentálny algoritmus, ktorého pochopenie je kľúčové pre všetkých, ktorí sa zaoberajú spracovaním dát, programovaním alebo analýzou algoritmov. Pomáha nám pochopiť základné princípy prehľadávania dátových štruktúr a porovnať ho s inými, zložitejšími metódami. ## Princíp lineárneho vyhľadávania > **Lineárne vyhľadávanie**, známe aj ako **sekvenčné vyhľadávanie**, je algoritmus, ktorý postupne prechádza každý prvok v zozname od začiatku až do momentu, keď nájde hľadanú položku alebo kým neprehľadá celý zoznam. Princíp je veľmi jednoduchý: začneme na prvej pozícii zoznamu a porovnáme aktuálny prvok s tým, čo hľadáme. Ak sa zhodujú, našli sme hľadanú položku a vrátime jej pozíciu (index). Ak sa nezhodujú, prejdeme na ďalší prvok v zozname a proces opakujeme. Pokračujeme tak dlho, kým buď nájdeme položku, alebo kým neprejdeme všetky prvky v zozname. Ak sa dostaneme na koniec zoznamu a položku sme nenašli, znamená to, že sa v zozname nenachádza. ### Pseudokód lineárneho vyhľadávania Pre lepšie pochopenie si môžeme predstaviť pseudokód, ktorý popisuje logiku algoritmu: ``` funkcia linearneVyhladavanie(zoznam, hladanaPolozka): pre kazdy index i od 0 do dlzky(zoznam) - 1: ak zoznam[i] je rovny hladanaPolozka: vrat index i vrat -1 (položka nenájdená) ``` ## Podmienka usporiadania zoznamu Jednou z hlavných výhod lineárneho vyhľadávania je jeho **univerzálnosť**. Na rozdiel od niektorých iných vyhľadávacích algoritmov, lineárne vyhľadávanie **nevyžaduje**, aby bol zoznam, v ktorom sa vyhľadáva, usporiadaný. Funguje rovnako efektívne (čo sa týka funkčnosti, nie časovej zložitosti) na zoznamoch s ľubovoľným poradím prvkov. * **Usporiadané dáta:** Algoritmus funguje. * **Neusporiadané dáta:** Algoritmus funguje. To ho robí ideálnym pre situácie, keď nie je praktické alebo možné usporiadať dáta pred vyhľadávaním. ## Počet krokov a časová zložitosť > **Časová zložitosť** je spôsob, akým meriame efektivitu algoritmu vzhľadom na veľkosť vstupu. Udáva, ako sa doba behu algoritmu mení s rastúcim počtom vstupných dát. Časová zložitosť lineárneho vyhľadávania sa označuje ako $O(n)$, kde $n$ je počet prvkov v zozname. To znamená, že čas potrebný na vykonanie algoritmu rastie **lineárne** s počtom prvkov v zozname. * **Najlepší prípad (Best Case):** Ak je hľadaná položka hneď na prvej pozícii v zozname, algoritmus ju nájde okamžite. Vykoná sa iba $1$ porovnanie. Príklad: hľadáme $15$ v `[15, 8, 23, ...]`. * **Priemerný prípad (Average Case):** V priemere musí algoritmus prejsť približne polovicu zoznamu, kým nájde hľadanú položku, t. j. približne $n/2$ porovnaní. * **Najhorší prípad (Worst Case):** Ak sa hľadaná položka nachádza na poslednej pozícii v zozname, alebo ak sa v zozname vôbec nenachádza, algoritmus musí prejsť celý zoznam. Vykoná sa $n$ porovnaní. Príklad: hľadáme $7$ v `[15, 8, 23, 4, 42, 10, 7]` alebo hľadáme $99$ v tomto zozname. Pre malé zoznamy je lineárne vyhľadávanie dostatočne rýchle. Avšak, pre veľmi veľké zoznamy (napríklad milióny položiek) môže byť $O(n)$ pomerne pomalé, pretože čas potrebný na vyhľadávanie rastie priamo úmerne s veľkosťou zoznamu. Ak sa zoznam zdvojnásobí, zdvojnásobí sa aj čas potrebný na vyhľadávanie v najhoršom prípade. Did you know, že napriek svojej jednoduchosti je lineárne vyhľadávanie často jedinou možnosťou, ak dáta nie sú usporiadané a nemôžu byť usporiadané, alebo ak je zoznam veľmi malý? ## Praktický príklad lineárneho vyhľadávania Predstavme si, že máme zoznam čísel a chceme nájsť konkrétnu hodnotu. Máme zoznam čísel: $[15, 8, 23, 4, 42, 10, 7]$ a hľadáme číslo $4