Οι αλγόριθμοι αναζήτησης και ταξινόμησης είναι οι δημοφιλείς αλγόριθμοι σε οποιεσδήποτε γλώσσες προγραμματισμού. Είναι η βάση για να κατανοήσουμε τις βασικές αρχές του προγραμματισμού. Ένας τέτοιος δημοφιλής αλγόριθμος αναζήτησης είναι το Binary Search in . Σε αυτό το άρθρο, θα σας πω όλα σχετικά με την εφαρμογή του.
Τα παρακάτω θέματα καλύπτονται σε αυτό το άρθρο:
Ας αρχίσουμε!
Τι είναι η δυαδική αναζήτηση;
Δυαδική αναζήτηση σε είναι ένα αλγόριθμος αναζήτησης που βρίσκει τη θέση μιας τιμής στόχου σε μια ταξινομημένη πίνακας . Δυαδική αναζήτηση συγκρίνει την τιμή στόχου με το μεσαίο στοιχείο του πίνακα. Τολειτουργεί μόνο σε ένα ταξινομημένο σύνολο στοιχείων. Για να χρησιμοποιήσετε τη δυαδική αναζήτηση σε μια συλλογή, το πρέπει πρώτα να ταξινομηθούν.
Οταν ο χρησιμοποιείται για την εκτέλεση λειτουργιών σε ένα ταξινομημένο σύνολο, ο αριθμός των επαναλήψεων μπορεί πάντα να μειωθεί με βάση την τιμή που αναζητάται. Μπορείτε να δείτε στο παραπάνω στιγμιότυπο εύρεσης του μεσαίο στοιχείο . Η αναλογία της δυαδικής αναζήτησης είναι να χρησιμοποιήσετε τις πληροφορίες στις οποίες ταξινομήθηκε ο πίνακας και να μειώσετε την πολυπλοκότητα του χρόνου O (ημερολόγιο n) .
Υλοποίηση αλγορίθμου δυαδικής αναζήτησης
Ας ρίξουμε μια ματιά στον παρακάτω ψευδο κώδικα για να τον κατανοήσουμε καλύτερα.
Διαδικασία binary_search A & larr ταξινομημένο πίνακα n & larr μέγεθος του πίνακα x & larr τιμή προς αναζήτηση Ορισμός χαμηλής = 1 Ορισμός υψηλού = n ενώ x δεν βρέθηκε εάν υψηλήΕξήγηση:
Βήμα 1: Πρώτα, συγκρίνετε το x με το μεσαίο στοιχείο.
Βήμα 2: Εάν το x ταιριάζει με το μεσαίο στοιχείο, τότε πρέπει να επιστρέψετε το μέσο ευρετήριο.
Βήμα 3: Διαφορετικά, Εάν το x είναι μεγαλύτερο από το μεσαίο στοιχείο, τότε το x μπορεί να βρίσκεται μόνο στη δεξιά μισή συστοιχία μετά το μεσαίο στοιχείο. Ως εκ τούτου επαναλαμβάνετε το σωστό μισό.
Βήμα 4: Διαφορετικά, εάν (το x είναι μικρότερο), επαναλάβετε το αριστερό μισό.
Έτσι πρέπει να αναζητήσετε το στοιχείο στο συγκεκριμένο πίνακα.
t sql ημερομηνία δεδομένων τύπουΑς δούμε τώρα πώς να εφαρμόσουμε αναδρομικά μια δυαδική αλγόριθμο αναζήτησης. Το παρακάτω πρόγραμμα δείχνει το ίδιο.
Αναδρομική δυαδική αναζήτηση
δημόσια τάξη BinarySearch {// Εφαρμογή Java της αναδρομικής δυαδικής αναζήτησης // Επιστροφή δείκτη του x εάν υπάρχει στο arr [l..h], αλλιώς return -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Εάν το στοιχείο υπάρχει στο ίδιο το κέντρο εάν (a [mid] == x) επιστροφή στα μέσα // Εάν στοιχείο είναι μικρότερο από τα μέσα, τότε μπορεί να υπάρχει μόνο στην αριστερή υποπεριοχή εάν (a [mid]> x) return binarySearch (arr, l, mid - 1, x) // Διαφορετικά, το στοιχείο μπορεί να υπάρχει μόνο στη δεξιά δευτεροβάθμια επιστροφή binarySearch (arr, mid + 1, h, x)} // Φτάνουμε εδώ όταν δεν υπάρχει στοιχείο στο array return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Το στοιχείο δεν υπάρχει') άλλο System.out.println ('Το στοιχείο βρέθηκε στο ευρετήριο' + res)}}Κατά την εκτέλεση του παραπάνω προγράμματος, θα εντοπίσει το στοιχείο που υπάρχει στο συγκεκριμένο ευρετήριο
Στοιχείο βρέθηκε στο ευρετήριο 2Αυτό μας φέρνει στο τέλος της δυαδικής αναζήτησης στο Ιάβα άρθρο. Ελπίζω ότι το βρήκατε ενημερωτικό και σας βοήθησε στην κατανόηση .
Δείτε το από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία εκμάθησης με δίκτυο περισσότερων από 250.000 ικανοποιημένων μαθητών σε όλο τον κόσμο. Είμαστε εδώ για να σας βοηθήσουμε σε κάθε βήμα στο ταξίδι σας, για να γίνετε εκτός από αυτές τις ερωτήσεις της συνέντευξης java. Έχουμε ένα πρόγραμμα σπουδών που έχει σχεδιαστεί για μαθητές και επαγγελματίες που θέλουν να γίνουν προγραμματιστές Java. Το μάθημα έχει σχεδιαστεί για να σας δώσει μια πρώτη αρχή στον προγραμματισμό Java και να σας εκπαιδεύσει τόσο για τις βασικές όσο και για τις προηγμένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.
Σε περίπτωση που αντιμετωπίζετε οποιαδήποτε δυσκολία κατά την εφαρμογή της δυαδικής αναζήτησης στο , παρακαλούμε να το αναφέρετε στην παρακάτω ενότητα σχολίων και θα επικοινωνήσουμε μαζί σας το νωρίτερο.