Linjär sökalgoritm (Linear Search) i C++- Förklaring, exempel och kod

Den linjära sökalgoritmen är en enkel metod som används för att hitta ett specifikt element i en lista. Denna algoritm fungerar genom att sekventiellt kontrollera varje element i listan tills det önskade elementet hittas eller hela listan genomkorsas.

Hur det fungerar

1. Börja från det första elementet i listan.
2. Jämför det aktuella elementet med målvärdet.
3. Om det aktuella elementet är lika med målvärdet, avslutas algoritmen och returnerar elementets position.
4. Om inte, fortsätt att iterera genom de återstående elementen i listan.
5. Om hela listan passeras utan att hitta målelementet, returnerar algoritmen ett värde som indikerar att det inte finns.

Exempel

Låt oss säga att vi har en lista med heltal och vi vill hitta talet 34 i listan.

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

1. Börja vid det första elementet: 12. Inte önskat antal.
2. Flytta till nästa element: 45. Inte önskat nummer.
3. Fortsätt med de återstående elementen: 67, 89, 34. Element 34 matchar önskat antal.
4. Algoritmen avslutar och returnerar positionen 34, vilket är 4.

Exempelkod i 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;  
}  

I det givna exemplet har vi använt linearSearch funktionen för att hitta talet 34 i listan över heltal. Resultatet blir positionen 34 i listan(positionerna börjar från 0) eller -1 om numret inte hittas.