Δυαδική αναζήτηση

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί το είδος Binary Search. Επίσης, θα βρείτε λειτουργικά παραδείγματα της δυαδικής αναζήτησης σε C, C ++, Java και Python.

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

Σε αυτήν την προσέγγιση, το στοιχείο αναζητείται πάντα στη μέση ενός τμήματος ενός πίνακα.

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

Δυαδική αναζήτηση λειτουργεί

Ο αλγόριθμος δυαδικής αναζήτησης μπορεί να εφαρμοστεί με δύο τρόπους που συζητούνται παρακάτω.

  1. Επαναληπτική μέθοδος
  2. Αναδρομική μέθοδος

Η αναδρομική μέθοδος ακολουθεί την προσέγγιση διαίρεσης και κατάκτησης.

Τα γενικά βήματα και για τις δύο μεθόδους συζητούνται παρακάτω.

  1. Ο πίνακας στον οποίο θα πραγματοποιηθεί η αναζήτηση είναι: Αρχικός πίνακας
    Ας x = 4είναι το στοιχείο προς αναζήτηση.
  2. Ορίστε δύο δείκτες χαμηλό και υψηλό στη χαμηλότερη και την υψηλότερη θέση αντίστοιχα. Ρύθμιση δεικτών
  3. Βρείτε το μεσαίο στοιχείο στο μέσο του πίνακα, δηλαδή. (arr(low + high)) / 2 = 6. Μεσαίο στοιχείο
  4. Εάν x == mid, τότε επιστρέψτε mid.Esese, συγκρίνετε το στοιχείο προς αναζήτηση με m.
  5. Εάν x> mid, συγκρίνετε το x με το μεσαίο στοιχείο των στοιχείων στη δεξιά πλευρά του μέσου. Αυτό γίνεται με τον καθορισμό χαμηλό σε low = mid + 1.
  6. Διαφορετικά, συγκρίνετε το x με το μεσαίο στοιχείο των στοιχείων στην αριστερή πλευρά του μέσου. Αυτό γίνεται με τη ρύθμιση του υψηλού σε high = mid - 1. Εύρεση μέσου στοιχείου
  7. Επαναλάβετε τα βήματα 3 έως 6 έως ότου το χαμηλό φτάσει στο υψηλό. Μεσαίο στοιχείο
  8. x = 4βρίσκεται. Βρέθηκαν

Αλγόριθμος δυαδικής αναζήτησης

Μέθοδος επανάληψης

Κάντε έως ότου οι δείκτες χαμηλό και υψηλό συναντηθούν mid = (low + high) / 2 if (x == arr (mid)) επιστροφή στο μέσο του άλλου εάν (x> A (mid)) // x είναι στη δεξιά πλευρά χαμηλό = mid + 1 άλλο // x είναι ενεργοποιημένο η αριστερή πλευρά ψηλά = μέσα - 1

Αναδρομική μέθοδος

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid other if x <data (mid) // x είναι στο binary side search binary (arr, x, mid + 1, high) other // x είναι στη δεξιά πλευρά return binarySearch (arr, x, low, mid - 1)

Παραδείγματα Python, Java, C / C ++ (Επαναληπτική μέθοδος)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Παραδείγματα Python, Java, C / C ++ (Αναδρομική μέθοδος)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Πολυπλοκότητα δυαδικής αναζήτησης

Χρόνος πολυπλοκότητας

  • Καλύτερη πολυπλοκότητα περιπτώσεων :O(1)
  • Μέση πολυπλοκότητα περιπτώσεων :O(log n)
  • Χειρότερη περίπλοκη περίπτωση :O(log n)

Διαστημική πολυπλοκότητα

Η διαστημική πολυπλοκότητα της δυαδικής αναζήτησης είναι O(n).

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

  • Σε βιβλιοθήκες Java, .Net, C ++ STL
  • Κατά τον εντοπισμό σφαλμάτων, η δυαδική αναζήτηση χρησιμοποιείται για τον εντοπισμό του τόπου όπου συμβαίνει το σφάλμα.

ενδιαφέροντα άρθρα...