Algorytm wyszukiwania liniowego (Linear Search) w C++- wyjaśnienie, przykład i kod

Algorytm wyszukiwania liniowego to prosta metoda używana do znalezienia określonego elementu na liście. Algorytm ten polega na sekwencyjnym sprawdzaniu każdego elementu na liście, aż do znalezienia żądanego elementu lub przejrzenia całej listy.

Jak to działa

1. Zacznij od pierwszego elementu na liście.
2. Porównaj bieżący element z wartością docelową.
3. Jeśli bieżący element jest równy wartości docelowej, algorytm kończy działanie i zwraca pozycję elementu.
4. Jeśli nie, kontynuuj przeglądanie pozostałych elementów na liście.
5. Jeśli cała lista zostanie przeszukana bez znalezienia elementu docelowego, algorytm zwraca wartość wskazującą, że nie znaleziono.

Przykład

Powiedzmy, że mamy listę liczb całkowitych i chcemy znaleźć na liście liczbę 34.

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

1. Zacznij od pierwszego elementu: 12. Nie żądana liczba.
2. Przejdź do następnego elementu: 45. Nie żądana liczba.
3. Kontynuuj z pozostałymi elementami: 67, 89, 34. Element 34 pasuje do żądanej liczby.
4. Algorytm kończy działanie i zwraca pozycję 34, czyli 4.

Przykładowy kod w 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;  
}  

W podanym przykładzie użyliśmy tej linearSearch funkcji do znalezienia liczby 34 na liście liczb całkowitych. Wynikiem będzie pozycja 34 na liście(pozycje zaczynają się od 0) lub -1 jeśli numer nie zostanie znaleziony.