binary search algorithm java implementation examples
Αυτό το σεμινάριο θα εξηγήσει τη δυαδική αναζήτηση και την αναδρομική δυαδική αναζήτηση στην Java μαζί με τον αλγόριθμο, την εφαρμογή και τον κώδικα δυαδικών κωδικών πρόσβασης δυαδικού κώδικα:
Μια δυαδική αναζήτηση σε Java είναι μια τεχνική που χρησιμοποιείται για την αναζήτηση μιας στοχευμένης τιμής ή κλειδιού σε μια συλλογή. Είναι μια τεχνική που χρησιμοποιεί την τεχνική «διαίρεση και κατάκτηση» για αναζήτηση ενός κλειδιού.
Η συλλογή στην οποία πρόκειται να εφαρμοστεί η δυαδική αναζήτηση για αναζήτηση ενός κλειδιού πρέπει να ταξινομηθεί με αύξουσα σειρά.
Συνήθως, οι περισσότερες από τις γλώσσες προγραμματισμού υποστηρίζουν τεχνικές γραμμικής αναζήτησης, δυαδικής αναζήτησης και κατακερματισμού που χρησιμοποιούνται για την αναζήτηση δεδομένων στη συλλογή. Θα μάθουμε κατακερματισμό στα επόμενα σεμινάρια μας.
=> Επισκεφθείτε εδώ για να μάθετε Java από το μηδέν.
Τι θα μάθετε:
Δυαδική αναζήτηση στην Ιάβα
Η γραμμική αναζήτηση είναι μια βασική τεχνική. Σε αυτήν την τεχνική, ο πίνακας διασχίζεται διαδοχικά και κάθε στοιχείο συγκρίνεται με το κλειδί έως ότου βρεθεί το κλειδί ή φτάσει το τέλος του πίνακα.
Η γραμμική αναζήτηση χρησιμοποιείται σπάνια σε πρακτικές εφαρμογές. Η δυαδική αναζήτηση είναι η πιο συχνά χρησιμοποιούμενη τεχνική, καθώς είναι πολύ πιο γρήγορη από μια γραμμική αναζήτηση.
Η Java παρέχει τρεις τρόπους για να πραγματοποιήσετε μια δυαδική αναζήτηση:
ενεργοποίηση θύρας έναντι προώθησης θύρας
- Χρησιμοποιώντας την επαναληπτική προσέγγιση
- Χρησιμοποιώντας μια αναδρομική προσέγγιση
- Χρησιμοποιώντας τη μέθοδο Arrays.binarySearch ().
Σε αυτό το σεμινάριο, θα εφαρμόσουμε και θα συζητήσουμε και τις τρεις αυτές μεθόδους.
Αλγόριθμος για δυαδική αναζήτηση στην Ιάβα
Στη μέθοδο δυαδικής αναζήτησης, η συλλογή χωρίζεται επανειλημμένα σε μισό και το στοιχείο κλειδιού πραγματοποιείται αναζήτηση στο αριστερό ή το δεξί μισό της συλλογής, ανάλογα με το αν το κλειδί είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο της συλλογής.
Ένας απλός αλγόριθμος δυαδικής αναζήτησης έχει ως εξής:
- Υπολογίστε το μέσο στοιχείο της συλλογής.
- Συγκρίνετε τα βασικά στοιχεία με το μέσο στοιχείο.
- Εάν το κλειδί = μεσαίο στοιχείο, τότε επιστρέφουμε τη θέση του μεσαίου δείκτη για το κλειδί που βρέθηκε.
- Διαφορετικά Εάν το πλήκτρο> μεσαίο στοιχείο, τότε το κλειδί βρίσκεται στο δεξί μισό της συλλογής. Επαναλάβετε τα βήματα 1 έως 3 στο κάτω (δεξί) μισό της συλλογής.
- Διαφορετικό κλειδί
Όπως μπορείτε να δείτε από τα παραπάνω βήματα, στη Δυαδική αναζήτηση, τα μισά στοιχεία της συλλογής αγνοούνται αμέσως μετά την πρώτη σύγκριση.
Σημειώστε ότι η ίδια ακολουθία βημάτων ισχύει για επαναληπτική καθώς και για αναδρομική δυαδική αναζήτηση.
Ας παρουσιάσουμε τον αλγόριθμο δυαδικής αναζήτησης χρησιμοποιώντας ένα παράδειγμα.
Για παράδειγμα, πάρτε την ακόλουθη ταξινομημένη σειρά 10 στοιχείων.
Ας υπολογίσουμε τη μεσαία θέση του πίνακα.
Mid = 0 + 9/2 = 4
# 1) Κλειδί = 21
Πρώτον, θα συγκρίνουμε την τιμή κλειδιού με το στοιχείο (mid) και θα διαπιστώσουμε ότι η τιμή του στοιχείου στα mid = 21.
Έτσι βρίσκουμε αυτό το κλειδί = (mid). Εξ ου και το κλειδί βρίσκεται στη θέση 4 του πίνακα.
# 2) Κλειδί = 25
Συγκρίνουμε πρώτα την βασική τιμή με τα μέσα. Ως (21<25), we will directly search for the key in the upper half of the array.
Τώρα πάλι θα βρούμε το μέσο για το άνω μισό του πίνακα.
Mid = 4 + 9/2 = 6
πώς να χρησιμοποιήσετε ένα αρχείο βάζου
Η τιμή στην τοποθεσία (mid) = 25
Τώρα συγκρίνουμε το βασικό στοιχείο με το μεσαίο στοιχείο. Έτσι (25 == 25), ως εκ τούτου βρήκαμε το κλειδί στην τοποθεσία (mid) = 6.
Έτσι διαιρούμε επανειλημμένα τον πίνακα και συγκρίνοντας το βασικό στοιχείο με το μέσο, αποφασίζουμε σε ποιο μισό θα αναζητήσουμε το κλειδί. Η δυαδική αναζήτηση είναι πιο αποτελεσματική από την άποψη του χρόνου και της ορθότητας και είναι επίσης πολύ ταχύτερη.
Εφαρμογή δυαδικής αναζήτησης Java
Χρησιμοποιώντας τον παραπάνω αλγόριθμο, ας εφαρμόσουμε ένα πρόγραμμα δυαδικής αναζήτησης στην Java χρησιμοποιώντας την επαναληπτική προσέγγιση. Σε αυτό το πρόγραμμα, λαμβάνουμε ένα παράδειγμα πίνακα και εκτελούμε δυαδική αναζήτηση σε αυτόν τον πίνακα.
import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } } Παραγωγή:
Ο πίνακας εισόδου: (5, 10, 15, 20, 25, 30, 35)
Κλειδί προς αναζήτηση = 20
Το στοιχείο βρίσκεται στο ευρετήριο: 3
Το παραπάνω πρόγραμμα δείχνει μια επαναληπτική προσέγγιση της δυαδικής αναζήτησης. Αρχικά, δηλώνεται ένας πίνακας και, στη συνέχεια, καθορίζεται ένα κλειδί προς αναζήτηση.
Μετά τον υπολογισμό του μέσου του πίνακα, το κλειδί συγκρίνεται με το μέσο στοιχείο. Στη συνέχεια, ανάλογα με το εάν το κλειδί είναι μικρότερο ή μεγαλύτερο από το κλειδί, το κλειδί πραγματοποιείται αναζήτηση στο κάτω ή στο άνω μισό του πίνακα αντίστοιχα.
Αναδρομική δυαδική αναζήτηση στην Ιάβα
Μπορείτε επίσης να εκτελέσετε μια δυαδική αναζήτηση χρησιμοποιώντας την τεχνική αναδρομής. Εδώ, η μέθοδος δυαδικής αναζήτησης καλείται αναδρομικά μέχρι να βρεθεί το κλειδί ή να εξαντληθεί ολόκληρη η λίστα.
Το πρόγραμμα που εφαρμόζει μια αναδρομική δυαδική αναζήτηση δίνεται παρακάτω:
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } } Παραγωγή:
Λίστα εισόδου: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Το κλειδί προς αναζήτηση:
Το κλειδί βρίσκεται στη θέση: 3 στη λίστα
Χρησιμοποιώντας τη μέθοδο Arrays.binarySearch ().
Η κλάση Arrays στην Java παρέχει μια μέθοδο «binarySearch ()» που εκτελεί τη δυαδική αναζήτηση στο δεδομένο Array. Αυτή η μέθοδος παίρνει τον πίνακα και το κλειδί για αναζήτηση ως ορίσματα και επιστρέφει τη θέση του κλειδιού στον πίνακα. Εάν το κλειδί δεν βρεθεί, τότε η μέθοδος επιστρέφει -1.
Το παρακάτω παράδειγμα εφαρμόζει τη μέθοδο Arrays.binarySearch ().
import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } } Παραγωγή:
Η σειρά εισαγωγής: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Το κλειδί προς αναζήτηση: 50
Το κλειδί βρίσκεται στο ευρετήριο: 4 στον πίνακα.
Συχνές Ερωτήσεις
Ε # 1) Πώς γράφετε μια δυαδική αναζήτηση;
Απάντηση: Η δυαδική αναζήτηση πραγματοποιείται συνήθως διαιρώντας τον πίνακα σε μισά. Εάν το κλειδί προς αναζήτηση είναι μεγαλύτερο από το μεσαίο στοιχείο, τότε το πάνω μισό του πίνακα αναζητείται διαιρώντας περαιτέρω και αναζητώντας τον υπο-πίνακα έως ότου βρεθεί το κλειδί.
Ομοίως, εάν το κλειδί είναι μικρότερο από το μεσαίο στοιχείο, τότε το κλειδί πραγματοποιείται αναζήτηση στο κάτω μισό του πίνακα.
γιατί το linux είναι πιο γρήγορο από τα παράθυρα
Ε # 2) Πού χρησιμοποιείται η δυαδική αναζήτηση;
Απάντηση: Η δυαδική αναζήτηση χρησιμοποιείται κυρίως για την αναζήτηση ταξινομημένων δεδομένων σε εφαρμογές λογισμικού ειδικά όταν ο χώρος μνήμης είναι μικρός και περιορισμένος.
Q # 3) Ποιο είναι το μεγάλο O της δυαδικής αναζήτησης;
Απάντηση: Η χρονική πολυπλοκότητα της δυαδικής αναζήτησης είναι O (logn) όπου n είναι ο αριθμός των στοιχείων στον πίνακα. Η διαστημική πολυπλοκότητα της δυαδικής αναζήτησης είναι O (1).
Ε # 4) Είναι η δυαδική αναζήτηση αναδρομική;
Απάντηση: Ναί. Δεδομένου ότι η δυαδική αναζήτηση είναι ένα παράδειγμα στρατηγικής διαίρεσης και κατάκτησης και μπορεί να εφαρμοστεί με την επανάληψη. Μπορούμε να χωρίσουμε τον πίνακα σε μισά και να καλέσουμε την ίδια μέθοδο για να εκτελέσουμε τη δυαδική αναζήτηση ξανά και ξανά.
Q # 5) Γιατί ονομάζεται δυαδική αναζήτηση;
Απάντηση: Ο αλγόριθμος δυαδικής αναζήτησης χρησιμοποιεί μια στρατηγική διαίρεσης και κατάκτησης που κόβει επανειλημμένα τον πίνακα σε μισά ή δύο μέρη. Έτσι ονομάζεται δυαδική αναζήτηση.
συμπέρασμα
Η δυαδική αναζήτηση είναι η τεχνική αναζήτησης που χρησιμοποιείται συχνά στη Java. Η απαίτηση για μια δυαδική αναζήτηση να πραγματοποιείται είναι ότι τα δεδομένα πρέπει να ταξινομηθούν με αύξουσα σειρά.
Μια δυαδική αναζήτηση μπορεί να εφαρμοστεί είτε χρησιμοποιώντας επαναληπτική είτε αναδρομική προσέγγιση. Το μάθημα Arrays στην Java παρέχει επίσης τη μέθοδο «binarySearch» που εκτελεί δυαδική αναζήτηση σε ένα Array.
Στα επόμενα σεμινάρια μας, θα διερευνήσουμε διάφορες τεχνικές ταξινόμησης στην Java.
=> Παρακολουθήστε εδώ την απλή εκπαίδευση Java.
Συνιστώμενη ανάγνωση
- Επιλογή ταξινόμησης σε Java - Αλγόριθμος επιλογής ταξινόμησης & παραδείγματα
- Ταξινόμηση εισαγωγής σε Java - Αλγόριθμος ταξινόμησης εισαγωγής και παραδείγματα
- Δυαδική αναζήτηση Δέντρο C ++: Εφαρμογή BST και λειτουργίες με παραδείγματα
- Java Interface και Abstract Class Tutorial με παραδείγματα
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
- Bubble Sort In Java - Java Sorting Algorithms & Code Παραδείγματα
- Εκμάθηση συμβολοσειράς Java | Μέθοδοι συμβολοσειράς Java με παραδείγματα
- Τι είναι το Java Java | Java Vector Class Tutorial με παραδείγματα