Algoritem linearnega iskanja (Linear Search) v C++ – razlaga, primer in koda

Algoritem linearnega iskanja je preprosta metoda, ki se uporablja za iskanje določenega elementa na seznamu. Ta algoritem deluje tako, da zaporedoma preverja vsak element na seznamu, dokler ni najden želeni element ali dokler ni prevožen celoten seznam.

Kako deluje

1. Začnite od prvega elementa na seznamu.
2. Primerjajte trenutni element s ciljno vrednostjo.
3. Če je trenutni element enak ciljni vrednosti, se algoritem zaključi in vrne položaj elementa.
4. Če ne, nadaljujte s ponavljanjem po preostalih elementih na seznamu.
5. Če se preleti celoten seznam, ne da bi se našel ciljni element, algoritem vrne vrednost, ki označuje, da ni najden.

Primer

Recimo, da imamo seznam celih števil in želimo na seznamu najti številko 34.

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

1. Začnite pri prvem elementu: 12. Ni želeno število.
2. Premakni se na naslednji element: 45. Ni želena številka.
3. Nadaljujte s preostalimi elementi: 67, 89, 34. Element 34 se ujema z želeno številko.
4. Algoritem se zaključi in vrne položaj 34, kar je 4.

Primer kode 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 danem primeru smo uporabili linearSearch funkcijo za iskanje števila 34 na seznamu celih števil. Rezultat bo položaj 34 na seznamu(položaji se začnejo z 0) ali -1, če številka ni najdena.