Søgealgoritmer: Eksponentiel søgning forklaret

Eksponentiel søgning

Eksponentiel søgning, også kendt som fingersøgning, søger efter et element i et sorteret array ved at hoppe over 2^ielementer hver iteration, hvor jeg repræsenterer værdien af ​​loop-kontrolvariabel, og derefter kontrollere, om søgeelementet er til stede mellem sidste spring og det aktuelle spring.

Kompleksitet Værste tilfælde

O (log (N)) Ofte forvirret på grund af navnet, er algoritmen navngivet så ikke på grund af tidskompleksiteten. Navnet opstår som et resultat af algoritmens springende elementer med trin svarende til eksponenter på 2

Hvordan det virker

  1. Spring over matrixelementerne 2^iad gangen og søg efter tilstanden Array[2^(i-1)] < valueWanted < Array[2^i]. Hvis 2^ier større end længden på arrayet, skal du indstille den øvre grænse til arrayets længde.
  2. Foretag en binær søgning mellem Array[2^(i-1)]ogArray[2^i]

Koden

// 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; }