close

Αλγόριθμος δυαδικής αναζήτησης (Binary Search) στην PHP: Επεξήγηση, Βήματα και Παράδειγμα

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

Βήματα:

  1. Αρχικοποίηση του εύρους αναζήτησης: Ξεκινήστε επιλέγοντας το εύρος αναζήτησης από την πρώτη θέση left  έως την τελευταία θέση right  του πίνακα.
  2. Βρείτε το μεσαίο σημείο: Υπολογίστε το μεσαίο σημείο υπολογίζοντας τον μέσο όρο left των θέσεων και δεξιά. αυτό είναι το μεσαίο σημείο του εύρους αναζήτησης.
  3. Σύγκριση τιμών: Συγκρίνετε την τιμή στο μεσαίο σημείο με την τιμή στόχο.
  4. Αποτέλεσμα σύγκρισης χειρισμού: Εάν η τιμή στο μεσαίο σημείο ταιριάζει με την τιμή στόχο, επιστρέψτε αυτήν τη θέση. Εάν η τιμή στο μεσαίο σημείο είναι μικρότερη από την τιμή στόχο, ενημερώστε την αριστερή θέση σε μέση + 1 για αναζήτηση στο δεξί μισό. Εάν η τιμή στο μεσαίο σημείο είναι μεγαλύτερη από την τιμή στόχο, ενημερώστε τη δεξιά θέση στη μέση- 1 για αναζήτηση στο αριστερό μισό.
  5. Επανάληψη: Επαναλάβετε τα βήματα 2 έως 4 μέχρι να βρεθεί η τιμή ή να μην υπάρχουν άλλα στοιχεία για έλεγχο left > right.

Πλεονεκτήματα και μειονεκτήματα

Πλεονεκτήματα:

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

Μειονεκτήματα:

  • Ισχύει μόνο για ταξινομημένους πίνακες: Ο αλγόριθμος λειτουργεί μόνο σε ταξινομημένους πίνακες.
  • Μεταβλητός αριθμός βημάτων: Ο αριθμός των βημάτων που απαιτούνται για την εύρεση της τιμής εξαρτάται από τη θέση της στον πίνακα και μπορεί να κάνει πολλά βήματα για τιμές κοντά στα άκρα.

Παράδειγμα: Δυαδική αναζήτηση για εύρεση της τιμής 12 σε ταξινομημένο πίνακα στην PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Επεξήγηση του Παραδείγματος

  1. Ξεκινάμε με το αρχικό εύρος αναζήτησης από την πρώτη θέση left = 0 μέχρι την τελευταία θέση right = 6  του πίνακα.
  2. Υπολογίζουμε το μεσαίο σημείο(μέση) υπολογίζοντας τον μέσο όρο της αριστερής και της δεξιάς θέσης. mid = 3. Η τιμή στα μέσα είναι 12.
  3. Συγκρίνουμε την τιμή στο mid(12) με την τιμή στόχο(12) και βρίσκουμε ένα ταίριασμα, οπότε επιστρέφουμε τη θέση 3.
  4. Ο αλγόριθμος τελειώνει και βγάζουμε το αποτέλεσμα "Τιμή 12 που βρέθηκε στη θέση 3."