Ένας από τους πιο θεμελιώδεις αλγόριθμους στην επιστήμη των υπολογιστών είναι ο αλγόριθμος δυαδικής αναζήτησης. Μπορείτε να εφαρμόσετε τη Δυαδική Αναζήτηση χρησιμοποιώντας δύο μεθόδους: την επαναληπτική μέθοδο και την αναδρομική μέθοδο. Ενώ και οι δύο μέθοδοι έχουν την ίδια χρονική πολυπλοκότητα, η επαναληπτική μέθοδος είναι πολύ πιο αποτελεσματική όσον αφορά την πολυπλοκότητα του χώρου.
Η επαναληπτική μέθοδος έχει πολυπλοκότητα χώρου O(1) σε σύγκριση με O(logn) παράγονται με την αναδρομική μέθοδο. Λοιπόν, πώς μπορείτε να εφαρμόσετε τον αλγόριθμο δυαδικής αναζήτησης χρησιμοποιώντας την επαναληπτική μέθοδο σε C, C++ και Python;
Τι είναι η δυαδική αναζήτηση;
Η δυαδική αναζήτηση γνωστή και ως αναζήτηση μισού διαστήματος, λογαριθμική αναζήτηση ή δυαδική κοπή είναι ένας αλγόριθμος που αναζητά και επιστρέφει τη θέση ενός στοιχείου σε έναν ταξινομημένο πίνακα. Το στοιχείο αναζήτησης συγκρίνεται με το μεσαίο στοιχείο. Λαμβάνοντας τον μέσο όρο του κατώτερου και του ανώτερου ορίου, μπορείτε να βρείτε τα μεσαία στοιχεία.
Εάν το στοιχείο αναζήτησης είναι μεγαλύτερο από το μεσαίο στοιχείο, σημαίνει ότι όλα τα στοιχεία στην αριστερή πλευρά είναι μικρότερα από το στοιχείο αναζήτησης. Έτσι, ο έλεγχος μετατοπίζεται στη δεξιά πλευρά του πίνακα (αν ο πίνακας είναι σε αύξουσα σειρά) αυξάνοντας το κάτω όριο στην επόμενη θέση του μεσαίου στοιχείου.
Ομοίως, εάν το στοιχείο αναζήτησης είναι μικρότερο από το μεσαίο στοιχείο, σημαίνει ότι όλα τα στοιχεία στη δεξιά πλευρά είναι μεγαλύτερα από το στοιχείο αναζήτησης. Έτσι, το στοιχείο ελέγχου μετατοπίζεται στο αριστερό μέρος του πίνακα αλλάζοντας το άνω όριο στην προηγούμενη θέση του μεσαίου στοιχείου.
Αυτό μειώνει δραστικά τον αριθμό των συγκρίσεων σε σύγκριση με υλοποίηση γραμμικής αναζήτησης όπου ο αριθμός των συγκρίσεων ισούται με τον αριθμό των στοιχείων στο χειρότερο σενάριο. Αυτή η μέθοδος αποδεικνύεται πολύ χρήσιμη για την εύρεση αριθμών σε έναν τηλεφωνικό κατάλογο ή λέξεων σε ένα λεξικό.
Εδώ είναι μια διαγραμματική αναπαράσταση του Αλγόριθμος δυαδικής αναζήτησης:
Δυαδική αναζήτηση με χρήση C
Ακολουθήστε αυτά τα βήματα για να εφαρμόσετε τη δυαδική αναζήτηση χρησιμοποιώντας το C:
Ολόκληρος ο πηγαίος κώδικας του προγράμματος δυαδικής αναζήτησης που χρησιμοποιεί C, C++, Java και Python υπάρχει σε αυτό Αποθετήριο GitHub.
Το πρόγραμμα ορίζει μια συνάρτηση, binarySearch(), που επιστρέφει είτε το ευρετήριο της τιμής που βρέθηκε είτε -1 αν δεν υπάρχει:
#περιλαμβάνω <stdio.h>
ενθbinarySearch(ενθ arr[], ενθ arr_size, ενθ αριθμός_αναζήτησης){
/*... */
}
Η συνάρτηση λειτουργεί περιορίζοντας επαναληπτικά τον χώρο αναζήτησης. Δεδομένου ότι η δυαδική αναζήτηση λειτουργεί σε ταξινομημένους πίνακες, μπορείτε να υπολογίσετε τη μέση που διαφορετικά δεν έχει νόημα. Μπορείτε είτε να ζητήσετε από τον χρήστη έναν ταξινομημένο πίνακα είτε να χρησιμοποιήσετε αλγόριθμους ταξινόμησης όπως τα Bubble ή Selection sort.
ο χαμηλός και υψηλός Οι μεταβλητές αποθηκεύουν τα ευρετήρια που αντιπροσωπεύουν τα όρια του τρέχοντος χώρου αναζήτησης. στα μέσα αποθηκεύει το ευρετήριο στη μέση:
ενθ χαμηλό = 0, υψηλό = arr_size - 1, μέσα;Το κύριο ενώ() Ο βρόχος θα περιορίσει τον χώρο αναζήτησης. Εάν η τιμή του χαμηλού δείκτη γίνει ποτέ μεγαλύτερη από τον υψηλό δείκτη, τότε ο χώρος αναζήτησης έχει εξαντληθεί, επομένως η τιμή δεν μπορεί να είναι παρούσα.
ενώ (χαμηλό <= υψηλό) {
/* συνεχίζει... [1] */
}
ΕΠΙΣΤΡΟΦΗ-1;
Μετά την ενημέρωση του μέσου σημείου στην αρχή του βρόχου, υπάρχουν τρία πιθανά αποτελέσματα:
- Εάν η τιμή στο μέσο είναι αυτή που αναζητούμε, επιστρέψτε αυτόν τον δείκτη.
- Εάν η τιμή του μέσου είναι μεγαλύτερη από αυτή που αναζητούμε, μειώστε το υψηλό.
- Εάν η τιμή του μέσου είναι μικρότερη, αυξήστε το χαμηλό.
/* [1] ...συνέχεια */
μεσαία = (χαμηλή + (υψηλή - χαμηλή)) / 2;
εάν (arr[mid] == search_number)
ΕΠΙΣΤΡΟΦΗ στα μέσα;
αλλούαν (arr[mid] > search_number)
υψηλό = μεσαίο - 1;
αλλού
χαμηλό = μεσαίο + 1;
Δοκιμάστε τη λειτουργία με την είσοδο του χρήστη. Χρήση scanf() για να λάβετε δεδομένα από τη γραμμή εντολών, συμπεριλαμβανομένου του μεγέθους του πίνακα, των περιεχομένων του και ενός αριθμού για αναζήτηση:
ενθκύριος(){
ενθ αρ[100], i, arr_size, search_number;
printf("Εισαγάγετε τον αριθμό των στοιχείων: ");
scanf("%ρε", &arr_size);
printf("Εισαγάγετε αριθμούς: ");για (i = 0; Εγώ < arr_size; i++) {
scanf("%ρε", &arr[i]);
}printf("Εισαγάγετε τον αριθμό για αναζήτηση: ");
scanf("%ρε", &αναζήτηση_αριθμός);i = binarySearch (arr, arr_size, search_number);
εάν (i==-1)
printf("Ο αριθμός δεν υπάρχει");
αλλού
printf("Ο αριθμός υπάρχει στη θέση %d", i + 1);
ΕΠΙΣΤΡΟΦΗ0;
}
Εάν βρείτε τον αριθμό, εμφανίστε τη θέση ή το ευρετήριό του, διαφορετικά ένα μήνυμα που λέει ότι ο αριθμός δεν υπάρχει.
Δυαδική αναζήτηση με χρήση C++
Μπορείτε να μετατρέψετε το πρόγραμμα C σε πρόγραμμα C++ εισάγοντας το Ροή εισόδου εξόδου και χρησιμοποιήστε namespace std για να αποφύγετε την επανάληψη πολλές φορές σε όλο το πρόγραμμα.
#περιλαμβάνω <iostream>
χρησιμοποιώντας χώρο ονομάτωνstd;Χρήση cout με χειριστή εξόρυξης << αντί printf() και cin με τελεστή εισαγωγής >> αντί scanf() και το πρόγραμμά σας C++ είναι έτοιμο.
printf("Εισαγάγετε τον αριθμό των στοιχείων: ");
cout <<"Εισαγάγετε τον αριθμό των στοιχείων: ";
scanf("%ρε", &arr_size);
cin >> arr_size;Δυαδική αναζήτηση με χρήση Python
Καθώς η Python δεν έχει ενσωματωμένη υποστήριξη για πίνακες, χρησιμοποιήστε λίστες. Ορίστε μια συνάρτηση, binarySearch(), που δέχεται τρεις παραμέτρους, τη λίστα, το μέγεθός της και έναν αριθμό για αναζήτηση:
defbinarySearch(arr, arr_size, search_number):
χαμηλό = 0
υψηλό = arr_size - 1
ενώ χαμηλό <= υψηλό:
μεσαίο = χαμηλό + (υψηλό-χαμηλό)//2
αν arr[mid] == search_number:
ΕΠΙΣΤΡΟΦΗ στα μέσα
ελιφ arr[mid] > search_number:
υψηλό = μεσαίο - 1
αλλού:
χαμηλό = μεσαίο + 1
ΕΠΙΣΤΡΟΦΗ-1Αρχικοποιήστε δύο μεταβλητές, χαμηλός και υψηλός, για να χρησιμεύσει ως το κάτω και πάνω όριο της λίστας. Παρόμοια με την υλοποίηση C, χρησιμοποιήστε a ενώ βρόχο που περιορίζει τον χώρο αναζήτησης. Αρχικοποίηση στα μέσα για να αποθηκεύσετε τη μεσαία τιμή της λίστας. Η Python παρέχει τον τελεστή διαίρεσης ορόφου(//) που παρέχει τον μεγαλύτερο δυνατό ακέραιο.
Κάντε τις συγκρίσεις και περιορίστε το χώρο αναζήτησης έως ότου η μεσαία τιμή ισούται με τον αριθμό αναζήτησης. Εάν ο αριθμός αναζήτησης δεν υπάρχει, το στοιχείο ελέγχου θα επιστρέψει -1.
arr_size = int (εισαγωγή("Εισαγάγετε τον αριθμό των στοιχείων: "))
arr=[]
Τυπώνω("Εισαγάγετε αριθμούς: ", τέλος="")
για i στην περιοχή (0,arr_size):
arr.append(ενθ(εισαγωγή()))
αριθμός_αναζήτησης = int (εισαγωγή("Εισαγάγετε τον αριθμό για αναζήτηση: "))
αποτέλεσμα = δυαδική αναζήτηση (arr, arr_size, search_number)
εάν αποτέλεσμα == -1:
Τυπώνω("Ο αριθμός δεν υπάρχει")
αλλού:
print("Αριθμός είναι παρόν στη θέση ", (αποτέλεσμα + 1))Δοκιμάστε τη λειτουργία με την είσοδο του χρήστη. Χρήση εισαγωγή() για να λάβετε το μέγεθος της λίστας, τα περιεχόμενά της και έναν αριθμό για αναζήτηση. Χρήση int() για να πληκτρολογήσετε την είσοδο συμβολοσειράς που έγινε αποδεκτή από την Python ως προεπιλογή σε έναν ακέραιο. Για να προσθέσετε αριθμούς στη λίστα, χρησιμοποιήστε το προσαρτώ() λειτουργία.
Κλήση binarySearch() και περάστε τα επιχειρήματα. Εάν βρείτε τον αριθμό, εμφανίστε τη θέση ή το ευρετήριό του, διαφορετικά ένα μήνυμα που λέει ότι ο αριθμός δεν υπάρχει.
Έξοδος αλγόριθμου δυαδικής αναζήτησης
Ακολουθεί η έξοδος του αλγόριθμου δυαδικής αναζήτησης όταν το στοιχείο υπάρχει στον πίνακα:
Ακολουθεί η έξοδος του αλγόριθμου δυαδικής αναζήτησης όταν το στοιχείο δεν υπάρχει στον πίνακα:
Μάθετε τις δομές και τους αλγόριθμους βασικών δεδομένων
Η αναζήτηση είναι ένας από τους πρώτους αλγόριθμους που μαθαίνεις και συχνά ερωτάται σε διαγωνισμούς κωδικοποίησης, τοποθετήσεις και συνεντεύξεις. Μερικοί άλλοι αλγόριθμοι που πρέπει να μάθετε είναι οι αλγόριθμοι ταξινόμησης, κατακερματισμού, δυναμικού προγραμματισμού, αντιστοίχισης συμβολοσειρών και δοκιμών πρωταρχικότητας.
Επιπλέον, είναι σημαντικό να κατανοήσουμε τη χρονική και χωρική πολυπλοκότητα των αλγορίθμων. Είναι μια από τις πιο κρίσιμες έννοιες στην Επιστήμη των Υπολογιστών για τον προσδιορισμό της αποτελεσματικότητας οποιουδήποτε αλγορίθμου. Με γνώση των Δομών Δεδομένων και των Αλγορίθμων, είστε αναγκασμένοι να δημιουργήσετε τα καλύτερα προγράμματα.
