Sekvenčné vyhľadávanie

Tento algoritmus predstavuje najjednoduchší a prakticky jediný spôsob ako hľadať v Netriediť lineárnej dátovej štruktúre (pole či zoznamu). Ide o spôsob, ktorý zrejme použil každý z nás, keď sa snažil niečo rýchlo nájsť napríklad v poli. Na záver ukážem ako tento pomalý spôsob aspoň trochu urýchliť.

Keď nemáme pole zotriedené, ťažko nájdeme iný spôsob ako ísť a prvky postupne prechádzať (najčastejšie od začiatku do konca) a porovnávať s hľadanou hodnú. Tejto metóde sa hovorí sekvenčná vyhľadávania (anglicky sequential search), niekedy tiež lineárne vyhľadávanie alebo naivné vyhľadávania.

Časová zložitosť

Čo sa týka časovej zložitosti tejto metódy, asi vás neprekvapí, že nie je vôbec pekná. Zakaždým musí dôjsť minimálne k jednému porovnanie (v prípade, že hneď prvý prvok je ten, ktorý hľadáme) a maximálne dôjde kn nákupný (n je počet prvkov v našej štruktúre), priemerný počet porovnaní je potom okolo n / 2. Časová zložitosť je teda lineárna. Nikdy neprekročí ani dolnú ani hornú hranicu (nikdy nebude rýchlejší ako 1 a nikdy nebude pomalší ako n), označíme ju teda Θ (n), ak chcete O (n).

Implementácia

K algoritmu budeme potrebovať lineárnu dátovú štruktúru (pole), hľadaný prvok (x) a veľkosť dátové štruktúry. Poďme sa teda pozrieť na kód, ktorý je napísaný v jazyku C# (v ostatných jazykoch by bol veľmi podobný).

/* v pripade, ze vas jazyk nedokaze urcit velikost pole, bude treba predat jeste parametr n typu int, ktery bude urcovat velikost pole */
public static int sekvencniVyhledavani(int[] pole, int x)
{
    for (int i = 0; i < pole.Length; i++)
    {
        if (pole[i] == x)
            return i; // vraci index, pokud jsme hledany prvek nalezli
    }
    return -1; // pri neuspechu vracime -1
}

Kód asi netreba príliš popisovať, je veľmi jednoduchý. Máme jeden cyklus a v ňom jednu podmienku. Vracia sa index nájdeného čísla (v prípade úspechu) alebo -1 (v prípade neúspechu). Algoritmus sa dá samozrejme upraviť tak, aby vracal napríklad pravdivostná hodnoty alebo to čo práve potrebujeme.

Optimalizácia

Na začiatku som spomínal isté vylepšenia, ktoré vám teraz ukážem. Keď sa pozriete na kód vyššie, zistíte, že v podstate dvakrát používate operáciu porovnanie - tá prvá kontroluje, aby sme neprekročili veľkosť poľa a druhá zisťuje, či sa aktuálny prvok rovná x. Teraz teda skúsime odstrániť jednu podmienku jednoduchým trikom. Naše pole vytvoríme o jeden prvok väčší a ako posledný prvok dáme hodnotu, ktorú hľadáme (občas sa táto hodnota označuje ako zarážka). Potom teda cyklus vždy nájde hľadaný prvok a bude len potrebné zistiť, či bol prvok nájdený pred zarážkou. Tomuto algoritmu sa hovorí anglicky sequential search sentinel (slovensky by sa to dalo preložiť ako sekvenčné vyhľadávanie so zarážkou). Kód je tentoraz ešte jednoduchšie.

// opet muze byt potreba vlozit i velikost pole (n), pokud pracujete v jazyce, ktery ji neumi zjistit
public static int sekvencniVyhledavaniZarazka(int[] pole, int x)
{
    // vkladame hledany prvek na konec pole, pole musi byt o jeden prvek vetsi!
    pole[pole.Length - 1] = x;

    int i = 0;
    while (true)
    {
        if (pole[i] == x)
            return i; // vraci index nalezeneho prvku
        i++;
    }
}

Rýchlosť tohto algoritmu pocítite, až budete vyhľadávať vo veľkom množstve prvkov (v rámci státisícov). Stále sa však jedná o pomalé riešenie (na pomery iných vyhľadávacích algoritmov).

Samozrejme pripomeniem, že v mieste volanie funkcie / metódy bude potrebné zistiť, kde sme prvok našli, a to tým, že zistíme jednoduchú podmienkou, či sa vrátený index nerovná veľkosti poľa - 1.

Na záver by som chcel povedať, že tento algoritmus sa hodia len na malé dátové štruktúry a pre občasné používanie. Vždy si teda premyslite, či sa vám neoplatí poľa najskôr zotrieďiť a potom použiť napríklad binárne vyhľadávanie alebo použiť jeden z vyhľadávacích stromov.

PS Ako ste možno poznali, tento algoritmus je takmer nepoužiteľný, keď chceme do štruktúry vkladať alebo odoberať prvky (zvlášť u jazykov, ktoré neumožňujúce rozširovať veľkosť poľa), v týchto prípadoch rozhodne využite stromov.