Lekce 2 - Sekvenční vyhledávání

V minulé lekci, Hledání extrému (minima a maxima) v poli, jsme si ukázali algoritmus pro vyhledání extrému, neboli minima a maxima v poli.

Tento algoritmus představuje nejjednodušší a prakticky jediný způsob jak hledat v nesetříděné lineární datové struktuře (pole či seznamu). Jedná se o způsob, který nejspíš použil každý z nás, když se snažil něco rychle najít například v poli. Na závěr ukáži jak tento pomalý způsob alespoň trochu urychlit.

Když nemáme pole setříděné, stěží najdeme jiný způsob než jít a prvky postupně procházet (nejčastěji od začátku do konce) a porovnávat s hledanou hodnou. Této metodě se říká sekvenční vyhledávání (anglicky sequential search), někdy také lineární vyhledávání nebo naivní vyhledávání.

Časová složitost

Co se týče časové složitosti této metody, asi vás nepřekvapí, že není vůbec hezká. Pokaždé musí dojít minimálně k jednomu porovnání (v případě, že hned první prvek je ten, který hledáme) a maximálně dojde k n porovnání (n je počet prvků v naší struktuře), průměrný počet srovnání je poté kolem n/2. Časová složitost je tedy lineární. Nikdy nepřekročí ani dolní ani horní hranici (nikdy nebude rychlejší než 1 a nikdy nebude pomalejší než n), označíme ji tedy Θ(n), chcete-li O(n).

Implementace

K algoritmu budeme potřebovat lineární datovou strukturu (pole), hledaný prvek (x) a velikost datové struktury. Pojďme se tedy podívat na kód, který je napsaný v jazyce C# (v ostatních jazycích by byl velmi 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 není třeba příliš popisovat, je velice jednoduchý. Máme jeden cyklus a v něm jednu podmínku. Vrací se index nalezeného čísla (v případě úspěchu) nebo -1 (v případě neúspěchu). Algoritmus se dá samozřejmě upravit tak, aby vracel například pravdivostní hodnoty nebo to co zrovna potřebujeme.

Optimalizace

Na začátku jsem zmiňoval jisté vylepšení, které vám nyní ukáži. Když se podíváte na kód výše, zjistíte, že v podstatě dvakrát používáte operaci porovnání - ta první kontroluje, abychom nepřesáhli velikost pole a druhá zjišťuje, zdali se aktuální prvek rovná x. Nyní tedy zkusíme odstranit jednu podmínku jednoduchým trikem. Naše pole vytvoříme o jeden prvek větší a jako poslední prvek dáme hodnotu, kterou hledáme (občas se tato hodnota označuje jako zarážka). Pak tedy cyklus vždy nalezne hledaný prvek a bude jen zapotřebí zjistit, zda byl prvek nalezen ještě před zarážkou. Tomuto algoritmu se říká anglicky sequential search sentinel (česky by se to dalo přeložit jako sekvenční vyhledávání se zarážkou). Kód je tentokrát ještě jednodušší.

// 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++;
    }
}

Rychlost tohoto algoritmu pocítíte, až budete vyhledávat ve velkém množství prvků (v rámci statisíců). Stále se však jedná o pomalé řešení (na poměry jiných vyhledávacích algoritmů).

Samozřejmě připomenu, že v místě volání funkce/metody bude třeba zjistit, kde jsme prvek našli, a to tím, že zjistíme jednoduchou podmínkou, jestli se vrácený index nerovná velikosti pole - 1.

Na závěr bych chtěl říci, že tento algoritmus se hodí jen na malé datové struktury a pro občasné používání. Vždy si tedy promyslete, jestli se vám nevyplatí pole nejdříve setřídit a poté použít například binární vyhledávání anebo použít jeden z vyhledávacích stromů.

Jak jste možná poznali, tento algoritmus je téměř nepoužitelný, když chceme do struktury vkládat nebo odebírat prvky (zvlášť u jazyků, které neumožňující rozšiřovat velikost pole), v těchto případech rozhodně využijte stromů.

V další lekci, Binární vyhledávání, si ukážeme efektivní binární vyhledávání, které vyhledává prvky v setříděném poli.