Η γραμμική αναζήτηση, γνωστή και ως σειριακή αναζήτηση, είναι ένας απλός τρόπος για να βρούμε ένα συγκεκριμένο στοιχείο σε έναν πίνακα ή μια λίστα δεδομένων. Ας το εξηγήσουμε βήμα-βήμα και απλά:

Τι Είναι η Γραμμική Αναζήτηση;

Η γραμμική αναζήτηση είναι μια μέθοδος με την οποία ψάχνουμε για ένα συγκεκριμένο στοιχείο σε μια λίστα (ή πίνακα) με την εξής διαδικασία:

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

Βήματα της Γραμμικής Αναζήτησης

  1. Αρχίζουμε από το πρώτο στοιχείο: Αν η λίστα έχει 10 στοιχεία, ξεκινάμε από το πρώτο (θέση 0).
  2. Συγκρίνουμε το στοιχείο: Αν ψάχνουμε για τον αριθμό 25 και το πρώτο στοιχείο είναι 10, δεν είναι αυτό που ψάχνουμε.
  3. Προχωράμε στο επόμενο στοιχείο: Μετακινούμαστε στο δεύτερο στοιχείο της λίστας (θέση 1) και συγκρίνουμε ξανά.
  4. Επαναλαμβάνουμε: Συνεχίζουμε αυτή τη διαδικασία μέχρι να βρούμε το στοιχείο ή να φτάσουμε στο τέλος της λίστας.

Τι Συμβαίνει Όταν Βρούμε το Στοιχείο;

Αν βρούμε το στοιχείο που ψάχνουμε, επιστρέφουμε τη θέση (ή δείκτη) του στοιχείου στη λίστα. Για παράδειγμα, αν το βρούμε στη θέση 3, επιστρέφουμε το 3.

Τι Συμβαίνει Αν Δεν Βρούμε το Στοιχείο;

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

Ψευδογλώσσα για Γραμμική Αναζήτηση (Linear Search)

ΑΛΓΟΡΙΘΜΟΣ ΓραμμικήΑναζήτηση
    ΔΕΔΟΜΕΝΑ // λίστα, στοιχείο //
    ΜΕΤΑΒΛΗΤΕΣ // i, λίστα, στοιχείο //
    
    ΓΙΑ i ΑΠΟ 0 ΜΕΧΡΙ ΜΕΓΕΘΟΣ(λίστα) - 1
        ΑΝ λίστα[i] = στοιχείο ΤΟΤΕ
            ΕΠΙΣΤΡΟΦΗ i // Το στοιχείο βρέθηκε, επιστρέφει την θέση //
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΓΙΑ
    
    ΕΠΙΣΤΡΟΦΗ -1 // Το στοιχείο δεν βρέθηκε //
ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ
γραμμική-αναζήτηση-1-1Download

Κώδικας σε C# για Γραμμική Αναζήτηση (Linear Search)

using System;

class LinearSearchExample
{
    static int LinearSearch(int[] array, int target)
    {
        // Διάσχιση του πίνακα από την αρχή μέχρι το τέλος
        for (int i = 0; i < array.Length; i++)
        {
            // Έλεγχος αν το τρέχον στοιχείο του πίνακα είναι ίσο με το ζητούμενο στοιχείο
            if (array[i] == target)
            {
                return i; // Το στοιχείο βρέθηκε, επιστρέφει την θέση
            }
        }
        return -1; // Το στοιχείο δεν βρέθηκε
    }

    static void Main()
    {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int target = 5;

        int result = LinearSearch(array, target);

        if (result != -1)
        {
            Console.WriteLine($"Element found at index {result}");
        }
        else
        {
            Console.WriteLine("Element not found in the array");
        }
    }
}

Jump Search (Αναζήτηση με Άλματα)

Η αναζήτηση με αλμάτων (jump search) είναι ένας ειδικός αλγόριθμος αναζήτησης που εκμεταλλεύεται την ταξινομημένη φύση των δεδομένων για να μειώσει τον αριθμό των συγκρίσεων που απαιτούνται για να εντοπιστεί ένα στοιχείο. Ο αλγόριθμος αυτός είναι αποδοτικότερος από τη γραμμική αναζήτηση σε ταξινομημένα δεδομένα, καθώς ελαττώνει τον αριθμό των συγκρίσεων από O(n) σε O(√n), όπου n είναι το πλήθος των στοιχείων.

Βασικά χαρακτηριστικά της αναζήτησης με αλμάτων περιλαμβάνουν:

  1. Ταξινομημένα Δεδομένα: Η αναζήτηση με αλμάτων προϋποθέτει ότι τα δεδομένα είναι ταξινομημένα σε αύξουσα σειρά. Αυτό είναι απαραίτητο για την αποτελεσματικότητα του αλγορίθμου.
  2. Αλγόριθμος Αναζήτησης: Ο αλγόριθμος διαμοιράζει τον πίνακα σε μικρά τμήματα ή “τμήματα αλμάτων” και στη συνέχεια ελέγχει το κάθε τμήμα για την περιοχή όπου μπορεί να βρίσκεται το στοιχείο που αναζητείτε.
  3. Επίδοση: Η αναζήτηση με αλμάτων είναι γρηγορότερη από τη γραμμική αναζήτηση, ειδικά για μεγάλα σύνολα δεδομένων. Εντοπίζει την περιοχή όπου πιθανόν βρίσκεται το στοιχείο με λιγότερες συγκρίσεις.

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

They followed her on to the deck. All the smoke and the houses had disappeared, and the ship was out in a wide space of sea very fresh and clear though pale in the early light. They had left London sitting on its mud. A very thin line of shadow tapered on the horizon, scarcely thick enough to stand the burden of Paris, which nevertheless rested upon it. They were free of roads, free of mankind, and the same exhilaration at their freedom ran through them all.

The ship was making her way steadily through small waves which slapped her and then fizzled like effervescing water, leaving a little border of bubbles and foam on either side. The colourless October sky above was thinly clouded as if by the trail of wood-fire smoke, and the air was wonderfully salt and brisk. Indeed it was too cold to stand still. Mrs. Ambrose drew her arm within her husband’s, and as they moved off it could be seen from the way in which her sloping cheek turned up to his that she had something private to communicate.