Recherche exponentielle

Le nom de cet algorithme de recherche peut être trompeur car il fonctionne en temps O(Log n). Le nom vient de la façon dont il recherche un élément.

Nous avons discuté, recherche linéaire , recherche binaire pour ce problème.
La recherche exponentielle comporte deux étapes :  

  1. Trouver la plage où l'élément est présent
  2. Effectuez une recherche binaire dans la plage trouvée ci-dessus.

Comment trouver la plage où l'élément peut être présent?  
L'idée est de commencer avec la taille de sous-tableau 1, de comparer son dernier élément avec x, puis d'essayer la taille 2, puis 4 et ainsi de suite jusqu'à ce que le dernier élément d'un sous-tableau ne soit pas supérieur. 
Une fois que nous avons trouvé un indice i (après doublement répété de i), nous savons que l'élément doit être présent entre i/2 et i (Pourquoi i/2 ? car nous n'avons pas pu trouver une valeur supérieure à l'itération précédente)
Ci-dessous sont les implémentations des étapes ci-dessus.

int binarySearch(int arr[], int, int, int);
  
// Returns position of first occurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
    // If x is present at first 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-1), 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;
}
  
// Driver code
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;
}
Modifié le: vendredi 12 août 2022, 20:29