C# Learning

Τι Είναι η Εκθετική Αναζήτηση;

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

Πώς Λειτουργεί;

1. Ψάχνουμε με “Βήματα”: Στην αρχή, δεν κοιτάμε όλους τους αριθμούς. Ξεκινάμε από την αρχή και διπλασιάζουμε το βήμα που κάνουμε κάθε φορά. Δηλαδή, αν αρχίσουμε από το πρώτο στοιχείο, μετά κοιτάμε το δεύτερο, το τέταρτο, το όγδοο, και ούτω καθεξής. Σκοπός είναι να βρούμε ένα σημείο που ο αριθμός που ψάχνουμε είναι μικρότερος από αυτό το σημείο.
2. Αναζητούμε Στην Περιοχή: Μόλις βρούμε το σημείο όπου ο αριθμός που ψάχνουμε είναι μικρότερος από αυτό, χρησιμοποιούμε μια πιο ακριβή μέθοδο αναζήτησης (όπως τον Δυαδικό Αλγόριθμο Αναζήτησης) για να βρούμε τον αριθμό ακριβώς.

Γιατί Είναι Χρήσιμο;

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

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

Ας δούμε πώς μπορούμε να το εφαρμόσουμε σε έναν υπολογιστή με ένα πρόγραμμα. Ακολουθούμε τα βήματα που περιγράψαμε.

using System;

class ExponentialSearchExample
{
    static void Main()
    {
        int[] numbers = { 1, 2, 4, 7, 11, 16, 23, 34, 47, 62 };
        int target = 23;

        int result = ExponentialSearch(numbers, target);

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

    static int ExponentialSearch(int[] array, int target)
    {
        // Εάν το πρώτο στοιχείο είναι το στόχος
        if (array.Length == 0)
        {
            return -1;
        }
        if (array[0] == target)
        {
            return 0;
        }

        // Βρίσκουμε το μέγεθος του εύρους αναζήτησης
        int index = 1;
        while (index < array.Length && array[index] <= target)
        {
            index *= 2;
        }

        // Εφαρμόζουμε Δυαδική Αναζήτηση στη μικρότερη περιοχή
        return BinarySearch(array, target, index / 2, Math.Min(index, array.Length - 1));
    }

    static int BinarySearch(int[] array, int target, int left, int right)
    {
        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (array[mid] == target)
            {
                return mid;
            }
            else if (array[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Τι Κάνει Το Πρόγραμμα;

1. Εκθετική Αναζήτηση: Ψάχνουμε σε “βήματα” διπλασιάζοντας κάθε φορά μέχρι να βρούμε ένα σημείο όπου ο αριθμός μας είναι μικρότερος.
2. Δυαδική Αναζήτηση: Όταν βρούμε το κατάλληλο τμήμα, χρησιμοποιούμε τη Δυαδική Αναζήτηση για να βρούμε ακριβώς τον αριθμό μας.

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