Φαντάσου ότι ψάχνεις ένα παιχνίδι σε μια μεγάλη βιβλιοθήκη γεμάτη με ράφια γεμάτα παιχνίδια. Αν η βιβλιοθήκη είναι πολύ μεγάλη και έχει πολλά ράφια, δεν θέλεις να ψάξεις παιχνίδι-παιχνίδι από την αρχή μέχρι το τέλος. Αντί να κοιτάς όλα τα παιχνίδια ένα-ένα, θα ήταν καλύτερα αν πήγαινες από ράφι σε ράφι με κάποια “άλματα” και κοίταζες μόνο τα πιο σημαντικά ράφια. Έτσι, μπορείς να βρεις το παιχνίδι πιο γρήγορα!

Αυτή η ιδέα είναι παρόμοια με την Αναζήτηση με Άλματα (Jump Search). Εδώ είναι πώς δουλεύει:

Βασικές Ιδέες για την Αναζήτηση με Άλματα

Καθόρισε Τα Άλματα: Σκέψου ένα βήμα ή άλμα που θα κάνεις. Αν έχεις 100 ράφια, μπορείς να αποφασίσεις να πηγαίνεις κάθε 10 ράφια. Έτσι, αν ψάχνεις στο ράφι 30, θα κοιτάξεις πρώτα το ράφι 10, μετά το ράφι 20, και μετά το ράφι 30.

Έλεγξε Άλματα: Εάν το παιχνίδι που ψάχνεις είναι στο ράφι 30, κοιτάς μόνο εκείνα τα ράφια που είναι κοντά σε αυτό το ράφι. Στο παράδειγμα, αυτό σημαίνει ότι αν βρεις ότι το παιχνίδι σου είναι κοντά στο ράφι 30, τότε κοιτάς όλα τα ράφια μέχρι να βρεις το σωστό παιχνίδι.

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

Πώς Λειτουργεί στην C#

Ας δούμε πώς μπορούμε να εφαρμόσουμε την Αναζήτηση με Άλματα σε ένα πρόγραμμα στην C#. Θα δημιουργήσουμε ένα πρόγραμμα που ψάχνει έναν αριθμό σε έναν ταξινομημένο πίνακα αριθμών χρησιμοποιώντας αυτή τη μέθοδο.

using System;

class JumpSearchExample
{
    static void Main()
    {
        int[] array = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 };
        int target = 15;

        int result = JumpSearch(array, target);
        if (result != -1)
        {
            Console.WriteLine($"Ο αριθμός {target} βρέθηκε στη θέση {result}.");
        }
        else
        {
            Console.WriteLine($"Ο αριθμός {target} δεν βρέθηκε.");
        }
    }

    static int JumpSearch(int[] array, int target)
    {
        int length = array.Length;
        int jump = (int)Math.Sqrt(length); // Καθορίστε το μέγεθος του άλματος
        int prev = 0;

        // Βρείτε το μπλοκ όπου μπορεί να βρίσκεται το target
        while (array[Math.Min(jump, length) - 1] < target)
        {
            prev = jump;
            jump += (int)Math.Sqrt(length);
            if (prev >= length)
                return -1;
        }

        // Κοιτάξτε μέσα στο μπλοκ που βρήκατε
        for (int i = prev; i < Math.Min(jump, length); i++)
        {
            if (array[i] == target)
                return i;
        }

        return -1; // Εάν δεν βρείτε το target
    }
}

Εξήγηση Κώδικα

Καθόρισε Άλματα: Χρησιμοποιούμε την τετραγωνική ρίζα του μήκους του πίνακα για να καθορίσουμε το μέγεθος του άλματος. Για παράδειγμα, αν ο πίνακας έχει 100 στοιχεία, το άλμα θα είναι 10.

Βρείτε το Μπλοκ: Ψάχνουμε για το σωστό μπλοκ του πίνακα όπου μπορεί να βρίσκεται ο αριθμός. Αν το μπλοκ που ψάχνουμε είναι μεγαλύτερο από το target, κοιτάμε όλα τα στοιχεία μέσα σε αυτό το μπλοκ.

Έλεγξε Το Μπλοκ: Κοιτάμε μέσα στο μπλοκ για να βρούμε τον αριθμό μας.

Αυτή η μέθοδος είναι χρήσιμη για να βρίσκουμε στοιχεία γρήγορα, ειδικά αν έχουμε ένα μεγάλο ταξινομημένο πίνακα και δεν θέλουμε να ψάχνουμε στοιχείο-στοιχείο. Ελπίζω αυτή η εξήγηση να σε βοήθησε να καταλάβεις πώς δουλεύει η Αναζήτηση με Άλματα!

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