Lineáris keresési (Linear Search) algoritmus C++ nyelven – magyarázat, példa és kód

A lineáris keresési algoritmus egy egyszerű módszer, amellyel egy lista adott elemét kereshetjük meg. Ez az algoritmus úgy működik, hogy a lista minden elemét egymás után ellenőrzi, amíg meg nem találja a kívánt elemet, vagy a teljes listát be nem járja.

Hogyan működik

1. Kezdje a lista első elemétől.
2. Hasonlítsa össze az aktuális elemet a célértékkel.
3. Ha az aktuális elem megegyezik a célértékkel, az algoritmus leáll, és visszaadja az elem pozícióját.
4. Ha nem, folytassa az iterációt a lista többi elemén.
5. Ha a teljes listát a célelem megtalálása nélkül bejárjuk, az algoritmus a nem található értéket jelzi.

Példa

Tegyük fel, hogy van egy egész számok listája, és meg akarjuk találni a 34-es számot a listában.

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

1. Kezdje az első elemnél: 12. Nem a kívánt szám.
2. Ugrás a következő elemre: 45. Nem a kívánt szám.
3. Folytassa a többi elemmel: 67, 89, 34. A 34. elem megegyezik a kívánt számmal.
4. Az algoritmus befejezi és visszaadja a 34-es pozíciót, ami 4.

Példakód C++ nyelven

#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;  
}  

Az adott példában a linearSearch függvény segítségével megtaláltuk a 34-es számot az egész számok listájában. Az eredmény a 34. pozíció lesz a listában(a pozíciók 0-tól kezdődnek), vagy -1, ha a szám nem található.