Δυαδική αναζήτηση με χρήση Python | Aman Kharwal

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

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

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

1. Ξεκινά ορίζοντας ένα εύρος αναζήτησης που εκτείνεται σε ολόκληρο τον πίνακα.
2. Στη συνέχεια, συγκρίνει την τιμή στόχο με το μεσαίο στοιχείο του εύρους αναζήτησης.
3. Εάν η τιμή στόχου είναι ίση με το μεσαίο στοιχείο, ο στόχος βρίσκεται και επιστρέφει το ευρετήριό του.
4. Εάν η τιμή στόχος είναι μικρότερη από το μεσαίο στοιχείο, ο αλγόριθμος απορρίπτει το πάνω μισό του εύρους αναζήτησης και επαναλαμβάνει το βήμα 2 με το κάτω μισό.
5. Εάν η τιμή στόχος είναι μεγαλύτερη από το μεσαίο στοιχείο, ο αλγόριθμος απορρίπτει το κάτω μισό του εύρους αναζήτησης και επαναλαμβάνει το βήμα 2 με το επάνω μισό.
6. Επαναλαμβάνει τα βήματα 2 έως 5 έως ότου βρεθεί η τιμή στόχος ή η περιοχή αναζήτησης είναι άδεια.

Παρακάτω είναι το είδος εισόδου και εξόδου που θα δείτε στο πρόβλημα της δυαδικής αναζήτησης στις συνεντεύξεις κωδικοποίησης:

• Είσοδος = [-1,0,3,5,9,12], στόχος = 9 | Έξοδος = 4

Δυαδική αναζήτηση με χρήση Python

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

def search(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [-1,0,3,5,9,12]
target = 9

print(search(nums, target))

Output: 4

Παρακάτω είναι πώς λειτουργεί ο παραπάνω κώδικας:

1. Ξεκινάμε με δύο μεταβλητές χαμηλή και υψηλή που ορίζουν το εύρος αναζήτησης ως ολόκληρο τον πίνακα.
2. Χρησιμοποιούμε έναν βρόχο while για να μειώσουμε επανειλημμένα στο μισό το διάστημα αναζήτησης μέχρι να βρεθεί το στοιχείο στόχος ή το διάστημα αναζήτησης να είναι κενό.
3. Σε κάθε επανάληψη του βρόχου, ο δείκτης του στοιχείου στο μέσο του διαστήματος αναζήτησης υπολογίζεται χρησιμοποιώντας τον τύπο (χαμηλό + υψηλό) // 2;
4. Συγκρίνουμε την τιμή στόχο με το μεσαίο στοιχείο του εύρους αναζήτησης:
   • Εάν η τιμή στόχος είναι ίση με το μεσαίο στοιχείο, έχουμε βρει τον στόχο μας και μπορούμε να επιστρέψουμε το ευρετήριό του.
   • Εάν η τιμή στόχος είναι μικρότερη από το μεσαίο στοιχείο, απορρίπτουμε το πάνω μισό του εύρους αναζήτησης και επαναλαμβάνουμε τη διαδικασία με το κάτω μισό.
   • Εάν η τιμή στόχος είναι μεγαλύτερη από το μεσαίο στοιχείο, απορρίπτουμε το κάτω μισό του εύρους αναζήτησης και επαναλαμβάνουμε τη διαδικασία με το επάνω μισό.
5. Εάν το στοιχείο στόχος δεν βρεθεί μετά από όλες τις επαναλήψεις του βρόχου, επιστρέφουμε ένα σήμα “δεν βρέθηκε”, το οποίο σε αυτήν την περίπτωση είναι -1.

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

Περίληψη

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