Lineaarinen (Linear Search) hakualgoritmi C++:ssa- selitys, esimerkki ja koodi

Lineaarinen hakualgoritmi on yksinkertainen menetelmä, jota käytetään tietyn elementin löytämiseen luettelosta. Tämä algoritmi toimii tarkistamalla peräkkäin jokaista luettelon elementtiä, kunnes haluttu elementti löytyy tai koko luettelo on käyty läpi.

Kuinka se toimii

1. Aloita luettelon ensimmäisestä elementistä.
2. Vertaa nykyistä elementtiä tavoitearvoon.
3. Jos nykyinen elementti on yhtä suuri kuin tavoitearvo, algoritmi lopettaa ja palauttaa elementin sijainnin.
4. Jos ei, jatka iterointia luettelon jäljellä olevien elementtien läpi.
5. Jos koko lista ajetaan läpi löytämättä kohdeelementtiä, algoritmi palauttaa arvon, joka ilmoittaa, että ei löydy.

Esimerkki

Oletetaan, että meillä on luettelo kokonaisluvuista ja haluamme löytää luvun 34 luettelosta.

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

1. Aloita ensimmäisestä elementistä: 12. Ei haluttu numero.
2. Siirry seuraavaan elementtiin: 45. Ei haluttu numero.
3. Jatka muilla elementeillä: 67, 89, 34. Elementti 34 vastaa haluttua numeroa.
4. Algoritmi lopettaa ja palauttaa paikan 34, joka on 4.

Esimerkkikoodi C++:ssa

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

Annetussa esimerkissä olemme käyttäneet linearSearch funktiota löytääksemme luvun 34 kokonaislukuluettelosta. Tuloksena on paikka 34 luettelossa(paikat alkavat 0:sta) tai -1, jos numeroa ei löydy.