Σε αυτό το παράδειγμα, θα μάθουμε να εφαρμόζουμε αλγόριθμο δυαδικής αναζήτησης στην Java.
Για να κατανοήσετε αυτό το παράδειγμα, θα πρέπει να γνωρίζετε τις ακόλουθες εφαρμογές προγραμματισμού Java:
- Java ενώ και κάνουμε… ενώ Loop
- Java αν… αλλιώς Δήλωση
- Πίνακες Java
Παράδειγμα: Πρόγραμμα Java για εφαρμογή αλγορίθμου δυαδικής αναζήτησης
import java.util.Scanner; // Binary Search in Java class Main ( int binarySearch(int array(), int element, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( // get index of mid element int mid = low + (high - low) / 2; // if element to be searched is the mid element if (array(mid) == element) return mid; // if element is less than mid element // search only the left side of mid if (array(mid) < element) low = mid + 1; // if element is greater than mid element // search only the right side of mid else high = mid - 1; ) return -1; ) public static void main(String args()) ( // create an object of Main class Main obj = new Main(); // create a sorted array int() array = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; // get input from user for element to be searched Scanner input = new Scanner(System.in); System.out.println("Enter element to be searched:"); // element to be searched int element = input.nextInt(); input.close(); // call the binary search method // pass arguments: array, element, index of first and last element int result = obj.binarySearch(array, element, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
Έξοδος 1
Εισαγάγετε το στοιχείο προς αναζήτηση: 6 Στοιχείο βρέθηκε στο ευρετήριο 3
Εδώ, χρησιμοποιήσαμε την Τάξη σαρωτή Java για να λάβουμε πληροφορίες από τον χρήστη. Με βάση την είσοδο από τον χρήστη, χρησιμοποιήσαμε τη δυαδική αναζήτηση για να ελέγξουμε εάν το στοιχείο υπάρχει στον πίνακα.
Μπορούμε επίσης να χρησιμοποιήσουμε την αναδρομική κλήση για να εκτελέσουμε την ίδια εργασία.
int binarySearch(int array(), int element, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // check if mid element is searched element if (array(mid) == element) return mid; // Search the left half of mid if (array(mid)> element) return binarySearch(array, element, low, mid - 1); // Search the right half of mid return binarySearch(array, element, mid + 1, high); ) return -1; )
Εδώ, η μέθοδος binarySearch()καλείται μέχρι να βρεθεί το στοιχείο ή, η ifσυνθήκη αποτυγχάνει.
Εάν θέλετε να μάθετε περισσότερα σχετικά με τον αλγόριθμο δυαδικής αναζήτησης, επισκεφθείτε τον Αλγόριθμο δυαδικής αναζήτησης.
