Linijinės paieškos (Linear Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

Linijinės paieškos algoritmas yra paprastas metodas, naudojamas konkrečiam sąrašo elementui rasti. Šis algoritmas veikia nuosekliai tikrindamas kiekvieną sąrašo elementą, kol randamas norimas elementas arba perkeliamas visas sąrašas.

Kaip tai veikia

1. Pradėkite nuo pirmojo sąrašo elemento.
2. Palyginkite esamą elementą su tiksline reikšme.
3. Jei dabartinis elementas yra lygus tikslinei reikšmei, algoritmas baigiasi ir grąžina elemento padėtį.
4. Jei ne, toliau kartokite likusius sąrašo elementus.
5. Jei perkeliamas visas sąrašas, nerandant tikslinio elemento, algoritmas grąžina reikšmę, rodančią nerasta.

Pavyzdys

Tarkime, kad turime sveikųjų skaičių sąrašą ir norime jame rasti skaičių 34.

Sąrašas: {12, 45, 67, 89, 34, 56, 23, 90}

1. Pradėkite nuo pirmojo elemento: 12. Ne norimas skaičius.
2. Pereikite prie kito elemento: 45. Ne norimas skaičius.
3. Tęskite su likusiais elementais: 67, 89, 34. 34 elementas atitinka norimą skaičių.
4. Algoritmas baigia ir grąžina 34 padėtį, kuri yra 4.

Kodo pavyzdys 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;  
}  

Pateiktame pavyzdyje naudojome linearSearch funkciją norėdami rasti skaičių 34 sveikųjų skaičių sąraše. Rezultatas bus 34 pozicija sąraše(pozicijos prasideda nuo 0) arba -1, jei skaičius nerastas.