Πώς να εφαρμόσετε έναν αλγόριθμο δυαδικής αναζήτησης σε Java χωρίς επανάληψη

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

Γεια σε όλους! Έχω δημοσιεύσει πολλούς αλγόριθμους και άρθρα δομής δεδομένων στο blog μου, αλλά αυτό είναι το πρώτο εδώ. Σε αυτό το άρθρο, θα εξετάσουμε δημοφιλείς θεμελιώδεις αλγόριθμους για συνεντεύξεις.

Ναι, το μαντέψατε σωστά: πρέπει να εφαρμόσετε μια δυαδική αναζήτηση στην Java και πρέπει να γράψετε επαναληπτικούς και αναδρομικούς αλγόριθμους δυαδικής αναζήτησης.

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

Η σύγκριση καθορίζει εάν το στοιχείο ισούται με την είσοδο, είναι μικρότερο από την είσοδο ή είναι μεγαλύτερο από την είσοδο.

Όταν το στοιχείο που συγκρίνεται ισούται με την είσοδο, η αναζήτηση σταματά και συνήθως επιστρέφει τη θέση του στοιχείου.

Εάν το στοιχείο δεν είναι ίσο με την είσοδο, τότε γίνεται σύγκριση για να προσδιοριστεί εάν η είσοδος είναι μικρότερη ή μεγαλύτερη από το στοιχείο.

Ανάλογα με το αποτέλεσμα, ο αλγόριθμος ξεκινά ξανά από την αρχή, αλλά ψάχνοντας μόνο το επάνω ή το κάτω μέρος των στοιχείων του πίνακα.

Εάν η είσοδος δεν βρίσκεται εντός του πίνακα, ο αλγόριθμος συνήθως εξάγει μια μοναδική τιμή που δείχνει αυτό σαν -1 ή απλώς ρίχνει ένα RuntimeException σε Java όπως το NoValueFoundException.

Οι αλγόριθμοι δυαδικής αναζήτησης συνήθως μειώνουν κατά το ήμισυ τον αριθμό των στοιχείων για έλεγχο με κάθε διαδοχική επανάληψη, εντοπίζοντας έτσι το δεδομένο στοιχείο (ή προσδιορίζοντας την απουσία του) σε λογαριθμικό χρόνο.

Ωστόσο, εάν δεν είστε εξοικειωμένοι με βασικούς αλγόριθμους αναζήτησης και ταξινόμησης, μπορείτε επίσης να συμμετάσχετε σε ένα μάθημα όπως Δομές δεδομένων και Αλγόριθμοι: Deep Dive Χρησιμοποιώντας Java για να μάθετε θεμελιώδεις αλγόριθμους.

Εάν η Java δεν είναι η επιλογή της γλώσσας σας, μπορείτε να βρείτε περισσότερες προτάσεις για JavaScript και Python σε αυτήν τη λίστα μαθημάτων αλγορίθμων.

Ωστόσο, αν προτιμάτε βιβλία, σας προτείνω να διαβάσετε ένα ολοκληρωμένο αλγόριθμο βιβλίο, όπως Εισαγωγή στους Αλγόριθμους του Thomas H. Cormen.

Ακολουθεί ένα δείγμα κώδικα που δείχνει τη λογική της επαναληπτικής δυαδικής αναζήτησης στην Java :

Εφαρμογή δυαδικής αναζήτησης σε Java

Ακολουθεί ένα δείγμα προγράμματος για την εφαρμογή δυαδικής αναζήτησης στην Java. Ο αλγόριθμος εφαρμόζεται αναδρομικά. Επίσης, ένα ενδιαφέρον γεγονός που πρέπει να γνωρίζετε σχετικά με την εφαρμογή δυαδικής αναζήτησης στην Java είναι ότι ο Joshua Bloch, συγγραφέας του διάσημου βιβλίου Effective Java, έγραψε τη δυαδική αναζήτηση στο "java.util.Arrays".

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

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

Η δομή δεδομένων δέντρου δυαδικής αναζήτησης εκμεταλλεύεται αυτόν τον αλγόριθμο και τακτοποιεί δεδομένα σε μια ιεραρχική δομή, έτσι ώστε να μπορείτε να αναζητήσετε οποιονδήποτε κόμβο στην ώρα O (logN).

Though, you must remember that in order to use binary search, you need a sorted list or array, so you also need to consider the cost of sorting when you consider using binary search algorithm in the real world.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures — Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

10 Algorithms books for Interviews

10 Data Structure and Algorithm Courses for Interviews

5 Free Courses to Learn Data Structure and Algorithms

Other Data Structure and Algorithms tutorials you may like

  • How to implement Quicksort algorithm in place in Java? (tutorial)
  • How to implement Binary Search Tree in Java? (solution)
  • How to implement Quicksort algorithm without recursion? (tutorial)
  • How to implement Insertion sort algorithm in Java? (tutorial)
  • Πώς να εφαρμόσετε τον αλγόριθμο ταξινόμησης Bubble στην Java; (φροντιστήριο)
  • Ποια είναι η διαφορά μεταξύ του αλγορίθμου ταξινόμησης βάσει σύγκρισης και μη σύγκρισης; (απάντηση)
  • Πώς να εφαρμόσετε την Ταξινόμηση κάδου στην Java; (φροντιστήριο)
  • Πώς να εφαρμόσετε έναν αλγόριθμο δυαδικής αναζήτησης χωρίς επανάληψη στην Java; (φροντιστήριο)
  • 50+ Μαθήματα Δομής Δεδομένων και Αλγορίθμων για Προγραμματιστές (ερωτήσεις)

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

PS - Εάν ενδιαφέρεστε σοβαρά να βελτιώσετε τις δεξιότητές σας στους Αλγόριθμους, νομίζω ότι οι Δομές Δεδομένων και Αλγόριθμοι: Το Deep Dive Η χρήση Java είναι το καλύτερο για να ξεκινήσετε.