Vyhledávací algoritmy

V této části si ukážeme dva vyhledávací algoritmy, které můžeme použít při hledání hodnot v poli. Jeden z nich pravděpodobně znáte a ten druhý byl už vlastně ukázaný v části 'Postup při řešení problému'.

Linear Search

Asi nejjednodušší způsob hledání položky v poli je celé pole projet for cyklem a ptát se jestli se nějaká položka rovná hledané hodnotě. Tento způsob ukazuje následující ukázka:

function linearSearch(pole, hodnota) {
    for (let i = 0; i < pole.length; i++) {
        // pokud se hledaná hodnota nachází na tomto indexu pole,
        // tak jsme hodnotu našli a vrátíme její index
        if (pole[i] === hodnota) return i;
    }
    // pokud jsme hledanou hodnotu v poli nenašli, vrátíme -1
    return -1
}

const index = linearSearch([5, 1, 3, 8, 6], 3);
console.log("Hledaná položka se nachází na indexu: " + index);

Časová náročnost tohoto způsobu je O(n), protože čím více má pole položek, tím více může (ale nemusí) proběhnout cyklů. Pokud pole, ve kterém vyhledáváme není seřazené, tak pravděpodobně neexistuje lepší způsob jak vyhledávat, pokud ale je tak ano.

Binary Search

Tento algoritmus slouží pro vyhledávání položky v seřazeném poli. Díky tomu, že hledáme hodnotu v seřazeném poli, tak nemusíme celé pole projíždět for cyklem jako u předchozího algoritmu. Můžeme se zeptat, jestli je hledaná položka nižší nebo vyšší než prostřední položka pole a podle toho se přesunout doprostřed levé části pole nebo pravé části pole. Tuto operaci můžeme několikrát opakovat a nakonec se k hledané položce dostaneme nebo dojdeme k závěru že hledaná položka v poli není.

Binary Search algoritmus byl již ukázan v části postup při řešení problému, ale rozhodl jsem se ho v této části ukázat ještě jednou a přidat k němu menší vizualizaci, která vám možná pomůže jej lépe pochopit.

const binarySearch = (pole, hodnota) => {
    let min = 0;
    let max = pole.length - 1;
    let middle = Math.trunc((min + max) / 2);

    while (pole[middle] !== hodnota && min <= max) {
        // zmenšení místa, které vymezují proměnné min a max
        // o polovinu, podle toho, kde se položka nachází
        if (hodnota < pole[middle]) {
            max = middle - 1;
        } else {
            min = middle + 1;
        }

        // získání prostřední položky mezi proměnnými min a max
        middle = Math.trunc((min + max) / 2);
    }
    // pokud se položka našla, tak se vrátí její index,
    // pokud ne, tak se vrátí -1
    return pole[middle] === hodnota ? middle : -1;
}

const index = binarySearch([2,5,6,9,13,15,28,30], 13);
console.log("Hledaná položka se nachází na indexu: " + index);

Časová náročnost Binary Search algoritmu je O(log n), což není vůbec špatné. Samozřejmě záleží také na tom jaké máme štěstí, občas můžeme položku třeba najít hned a časová náročnost by tak byla O(1).