Τι Είναι ο Κλασικός Δυαδικός Αλγόριθμος Αναζήτησης;

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

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

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

  1. Ξεκινάς με το βιβλίο ανοιχτό στη μέση: Ξεκινάς από το κέντρο της σειράς και ελέγχεις αν η σελίδα που ψάχνεις είναι αυτή που έχεις μπροστά σου.

  1. Αποφασίζεις αν να πας αριστερά ή δεξιά:
    • Αν η σελίδα που ψάχνεις είναι μικρότερη από τη σελίδα που έχεις μπροστά σου, τότε πρέπει να ψάξεις μόνο στη μισή αριστερή πλευρά.
    • Αν είναι μεγαλύτερη, τότε ψάχνεις μόνο στη μισή δεξιά πλευρά.

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

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

Ας δούμε πώς θα το κάναμε στην C#:

using System;

class Program
{
    static void Main()
    {
        // Δημιουργούμε έναν πίνακα με αριθμούς που είναι ήδη τακτοποιημένοι
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
        
        // Ο αριθμός που ψάχνουμε
        int target = 7;

        // Καλούμε τη μέθοδο BinarySearch για να βρούμε τον αριθμό
        int result = BinarySearch(numbers, target);

        // Εμφανίζουμε το αποτέλεσμα
        if (result != -1)
        {
            Console.WriteLine($"Ο αριθμός {target} βρέθηκε στη θέση {result}.");
        }
        else
        {
            Console.WriteLine($"Ο αριθμός {target} δεν βρέθηκε.");
        }
    }

    static int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        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. Πίνακας Αριθμών: Έχουμε έναν πίνακα αριθμών που είναι τακτοποιημένος από το 1 μέχρι το 19.
  2. Αναζήτηση: Ψάχνουμε για τον αριθμό 7.
  3. Συνάρτηση BinarySearch:
    • Ξεκινάμε από τη μέση του πίνακα.
    • Ελέγχουμε αν το στοιχείο είναι ο στόχος μας ή αν πρέπει να ψάξουμε αριστερά ή δεξιά.
    • Συνεχίζουμε τη διαδικασία με τη νέα περιοχή μέχρι να βρούμε το στοιχείο ή να καταλάβουμε ότι δεν υπάρχει.

Με αυτόν τον τρόπο, ο Δυαδικός Αλγόριθμος Αναζήτησης κάνει την αναζήτηση πιο γρήγορη γιατί δεν ψάχνει σε όλα τα στοιχεία, αλλά μόνο στη μισή κάθε φορά!

Κλασικός Δυαδικός Αλγόριθμος ΑναζήτησηςDownload