Algoritm de căutare liniară (Linear Search) în C++- Explicație, Exemplu și Cod

Algoritmul de căutare liniară este o metodă simplă folosită pentru a găsi un anumit element dintr-o listă. Acest algoritm funcționează prin verificarea succesivă a fiecărui element din listă până când este găsit elementul dorit sau este parcursă întreaga listă.

Cum functioneaza

1. Începeți de la primul element din listă.
2. Comparați elementul curent cu valoarea țintă.
3. Dacă elementul curent este egal cu valoarea țintă, algoritmul se încheie și returnează poziția elementului.
4. Dacă nu, continuați să repetați elementele rămase din listă.
5. Dacă întreaga listă este parcursă fără a găsi elementul țintă, algoritmul returnează o valoare care indică negăsit.

Exemplu

Să presupunem că avem o listă de numere întregi și că vrem să găsim numărul 34 în listă.

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

1. Începeți de la primul element: 12. Nu este numărul dorit.
2. Treceți la următorul element: 45. Nu este numărul dorit.
3. Continuați cu elementele rămase: 67, 89, 34. Elementul 34 se potrivește cu numărul dorit.
4. Algoritmul se termină și returnează poziția 34, care este 4.

Exemplu de cod în 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;  
}  

În exemplul dat, am folosit linearSearch funcția pentru a găsi numărul 34 în lista de numere întregi. Rezultatul va fi poziția 34 în listă(pozițiile încep de la 0) sau -1 dacă numărul nu este găsit.