Αλγόριθμοι αναζήτησης: Επεξήγηση εκθετικής αναζήτησης

Εκθετική αναζήτηση

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

Χειρότερη περίπτωση πολυπλοκότητας

O (log (N)) Συχνά συγχέεται λόγω του ονόματος, ο αλγόριθμος ονομάζεται έτσι όχι λόγω της πολυπλοκότητας του χρόνου. Το όνομα προκύπτει ως αποτέλεσμα των αλγορίθμων άλματα με βήματα ίσα με τους εκθέτες του 2

Πως δουλεύει

  1. Μεταβείτε τα 2^iστοιχεία του πίνακα κάθε φορά αναζητώντας την κατάσταση Array[2^(i-1)] < valueWanted < Array[2^i]. Εάν 2^iείναι μεγαλύτερο από το μήκος του πίνακα, τότε ορίστε το άνω όριο στο μήκος του πίνακα.
  2. Κάντε μια δυαδική αναζήτηση μεταξύ Array[2^(i-1)]καιArray[2^i]

Ο κώδικας

// C++ program to find an element x in a // sorted array using Exponential search. #include  using namespace std; int binarySearch(int arr[], int, int, int); // Returns position of first ocurrence of // x in array int exponentialSearch(int arr[], int n, int x) { // If x is present at firt location itself if (arr[0] == x) return 0; // Find range for binary search by // repeated doubling int i = 1; while (i < n && arr[i] <= x) i = i*2; // Call binary search for the found range. return binarySearch(arr, i/2, min(i, n), x); } // A recursive binary search function. It returns // location of x in given array arr[l..r] is // present, otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r>= l) { int mid = l + (r - l)/2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it // can only be present n left subarray if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid+1, r, x); } // We reach here when element is not present // in array return -1; } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr)/ sizeof(arr[0]); int x = 10; int result = exponentialSearch(arr, n, x); (result == -1)? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; }