Algoritam linearnog pretraživanja (Linear Search) u C++- objašnjenje, primjer i kod

Algoritam linearnog pretraživanja jednostavna je metoda koja se koristi za pronalaženje određenog elementa na popisu. Ovaj algoritam radi tako da uzastopno provjerava svaki element na popisu dok se ne pronađe željeni element ili dok se ne prijeđe cijeli popis.

Kako radi

1. Počnite od prvog elementa na popisu.
2. Usporedite trenutni element s ciljnom vrijednošću.
3. Ako je trenutni element jednak ciljnoj vrijednosti, algoritam se prekida i vraća položaj elementa.
4. Ako nije, nastavite iterirati kroz preostale elemente na popisu.
5. Ako se prijeđe cijeli popis bez pronalaska ciljnog elementa, algoritam vraća vrijednost koja označava da nije pronađen.

Primjer

Recimo da imamo popis cijelih brojeva i želimo pronaći broj 34 na popisu.

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

1. Počnite od prvog elementa: 12. Nije željeni broj.
2. Prijeđi na sljedeći element: 45. Nije željeni broj.
3. Nastavite s preostalim elementima: 67, 89, 34. Element 34 odgovara željenom broju.
4. Algoritam završava i vraća poziciju 34, što je 4.

Primjer koda u 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;  
}  

U navedenom primjeru upotrijebili smo linearSearch funkciju za pronalaženje broja 34 na popisu cijelih brojeva. Rezultat će biti pozicija 34 na popisu(pozicije počinju od 0) ili -1 ako broj nije pronađen.