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

Η Αναζήτηση Παρεμβολής (Interpolation Search) είναι ένα έξυπνο κόλπο για να βρεις το βιβλίο σου πιο γρήγορα από ότι αν κοιτούσες όλα τα βιβλία ένα-ένα. Αντί να ελέγχεις απλώς το μέσο σημείο της σειράς κάθε φορά, χρησιμοποιεί κάποιες πληροφορίες για να βρει μια καλύτερη θέση για να ελέγξει το βιβλίο σου.

Πώς Λειτουργεί η Αναζήτηση Παρεμβολής

Ξεκινάς από την αρχή: Έχεις μια μεγάλη σειρά αριθμών (όπως βιβλία), και ξέρεις το βιβλίο που ψάχνεις.

Υπολογισμός Θέσης: Αντί να ψάχνεις στο μέσο, η Αναζήτηση Παρεμβολής υπολογίζει μια θέση πιο κοντά σε αυτό που ψάχνεις. Σκέψου το σαν να κάνεις μια “εκτίμηση” για το που μπορεί να βρίσκεται το βιβλίο, βασισμένο σε ποιους αριθμούς έχεις στη σειρά.

Ελέγχεις την Υπολογισμένη Θέση: Πας στη θέση που υπολόγισες και κοιτάς αν το βιβλίο που ψάχνεις είναι εκεί.

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

Παράδειγμα στην C#

Ας δούμε πώς μπορούμε να εφαρμόσουμε αυτή την ιδέα στην C#:

using System;

class InterpolationSearchExample
{
    static void Main()
    {
        int[] array = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
        int target = 70;

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

    static int InterpolationSearch(int[] array, int target)
    {
        int low = 0;
        int high = array.Length - 1;

        while (low <= high && target >= array[low] && target <= array[high])
        {
            // Υπολογισμός της πιθανής θέσης
            int pos = low + ((target - array[low]) * (high - low) / (array[high] - array[low]));

            // Έλεγχος αν βρήκαμε το στόχο
            if (array[pos] == target)
            {
                return pos;
            }

            // Αν το στόχο είναι μικρότερος από την τιμή στη θέση pos, ψάχνουμε στο αριστερό κομμάτι
            if (array[pos] > target)
            {
                high = pos - 1;
            }
            // Αν το στόχο είναι μεγαλύτερος, ψάχνουμε στο δεξί κομμάτι
            else
            {
                low = pos + 1;
            }
        }

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

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

Εισαγωγή Αρχικών Τιμών: Ξεκινάμε από την αρχή και το τέλος του πίνακα.

Υπολογισμός Θέσης: Χρησιμοποιούμε την εξίσωση για να βρούμε μια πιθανή θέση του αριθμού που ψάχνουμε.

Έλεγχος και Προσαρμογή: Ελέγχουμε αν το βιβλίο (ή ο αριθμός) βρίσκεται στην υπολογισμένη θέση. Αν όχι, προσαρμόζουμε το εύρος αναζήτησης ανάλογα με το αν ο αριθμός είναι μικρότερος ή μεγαλύτερος από την τιμή στη θέση που υπολογίσαμε.

Επανάληψη ή Τερματισμός: Επαναλαμβάνουμε μέχρι να βρούμε το βιβλίο ή να εξαντλήσουμε τις πιθανές θέσεις.

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

Αναζήτηση Παρεμβολής (Interpolation Search)-1 Download