Lineární vyhledávací (Linear Search) algoritmus v C++- vysvětlení, příklad a kód

Algoritmus lineárního vyhledávání je jednoduchá metoda používaná k nalezení konkrétního prvku v seznamu. Tento algoritmus funguje tak, že postupně kontroluje každý prvek v seznamu, dokud není nalezen požadovaný prvek nebo dokud není prošel celý seznam.

Jak to funguje

1. Začněte od prvního prvku v seznamu.
2. Porovnejte aktuální prvek s cílovou hodnotou.
3. Pokud se aktuální prvek rovná cílové hodnotě, algoritmus se ukončí a vrátí polohu prvku.
4. Pokud ne, pokračujte v iteraci přes zbývající prvky v seznamu.
5. Pokud se projde celý seznam bez nalezení cílového prvku, algoritmus vrátí hodnotu označující nenalezeno.

Příklad

Řekněme, že máme seznam celých čísel a chceme v seznamu najít číslo 34.

Seznam: {12, 45, 67, 89, 34, 56, 23, 90}

1. Začněte od prvního prvku: 12. Není požadované číslo.
2. Přejděte na další prvek: 45. Není požadované číslo.
3. Pokračujte zbývajícími prvky: 67, 89, 34. Prvek 34 odpovídá požadovanému číslu.
4. Algoritmus skončí a vrátí pozici 34, což je 4.

Příklad kódu v C++

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

V uvedeném příkladu jsme použili linearSearch funkci k nalezení čísla 34 v seznamu celých čísel. Výsledkem bude pozice 34 v seznamu(pozice začínají od 0) nebo -1, pokud číslo nebude nalezeno.