Αλγόριθμος Γραμμικής Αναζήτησης (Linear Search) σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο αλγόριθμος γραμμικής αναζήτησης είναι μια απλή μέθοδος που χρησιμοποιείται για την εύρεση ενός συγκεκριμένου στοιχείου σε μια λίστα. Αυτός ο αλγόριθμος λειτουργεί ελέγχοντας διαδοχικά κάθε στοιχείο στη λίστα μέχρι να βρεθεί το επιθυμητό στοιχείο ή να διασχιστεί ολόκληρη η λίστα.

Πως δουλεύει

1. Ξεκινήστε από το πρώτο στοιχείο της λίστας.
2. Συγκρίνετε το τρέχον στοιχείο με την τιμή-στόχο.
3. Εάν το τρέχον στοιχείο ισούται με την τιμή στόχο, ο αλγόριθμος τερματίζει και επιστρέφει τη θέση του στοιχείου.
4. Εάν όχι, συνεχίστε την επανάληψη στα υπόλοιπα στοιχεία της λίστας.
5. Εάν ολόκληρη η λίστα διασχίζεται χωρίς να βρεθεί το στοιχείο προορισμού, ο αλγόριθμος επιστρέφει μια τιμή που υποδεικνύει ότι δεν βρέθηκε.

Παράδειγμα

Ας υποθέσουμε ότι έχουμε μια λίστα με ακέραιους αριθμούς και θέλουμε να βρούμε τον αριθμό 34 στη λίστα.

Λίστα: {12, 45, 67, 89, 34, 56, 23, 90}

1. Ξεκινήστε από το πρώτο στοιχείο: 12. Όχι ο επιθυμητός αριθμός.
2. Μεταβείτε στο επόμενο στοιχείο: 45. Δεν είναι ο επιθυμητός αριθμός.
3. Συνεχίστε με τα υπόλοιπα στοιχεία: 67, 89, 34. Το στοιχείο 34 ταιριάζει με τον επιθυμητό αριθμό.
4. Ο αλγόριθμος τερματίζει και επιστρέφει τη θέση του 34, που είναι 4.

Παράδειγμα κώδικα σε 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;  
}  

Στο συγκεκριμένο παράδειγμα, χρησιμοποιήσαμε τη linearSearch συνάρτηση για να βρούμε τον αριθμό 34 στη λίστα των ακεραίων. Το αποτέλεσμα θα είναι η θέση 34 στη λίστα(οι θέσεις ξεκινούν από το 0) ή -1 εάν ο αριθμός δεν βρεθεί.