Exponential Search Algorithm


Exponential search algorithm (also called doubling search, galloping search, Struzik search) is a search algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists.

Algorithm

Exponential search involves two basic steps:

  • Find range where element is present
  • Execute Binary Search algorithm in above found range.

** How to find the range where element may be present? **

The idea is to start with sub-list of size 1. Ccompare the last element of the list with the target element, then try size 2, then 4 and so on until last element of the list is not greater.
Once we find a location loc (after repeated doubling of list size), we know that the element must be present between loc/2 and loc.

Complexity

  • Worst case time complexity: O(log i) where i is the index of the element being searched.
  • Average case time complexity: O(log i)
  • Best case time complexity: O(1)
  • Space complexity: O(1)

Implementations

Implementation of exponential search algorithm in 9 languages that includes C, C++, Java, Go, JavaScript, PHP, Python, Rust and Swift.

  • C
  • C++

C


#include <stdio.h>
int 
min(int a, int b)
{
    return (a < b ? a : b);
}
int 
binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2; 
        if (arr[mid] == x)
            return (mid); 
        if (arr[mid] > x)
            return (binarySearch(arr, l, mid - 1, x));
         return (binarySearch(arr, mid + 1, r, x));
    }
    return (-1);
}
int 
exponentialSearch(int arr[], int n, int x)
{
    if (arr[0] == x)
        return (0);
    int i = 1;
    while (i < n && arr[i] <= x)
        i = i*2;
    return (binarySearch(arr, i / 2, min(i, n), x));
}
int 
main()
{
   int n;
   printf("Enter size of Array \n");
   scanf("%d", &n);
   int arr[n], i;
   printf("Enter %d integers in ascending order \n", n);
   for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
   int x;
   printf("Enter integer to be searched \n");
   scanf("%d", &x);
   int result = exponentialSearch(arr, n, x);
   if (result == -1)
        printf("%d is not present in array \n", x);
   else
        printf("%d is present at index %d \n", x, result);
   return (0);
}
  

C++


// C++ program to find an element x in a
// sorted array using Exponential search.
#include <cstdio>
#define min(a, b) ((a) < (b) ? (a) : (b))
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;
}
// 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;
}
  

Applications


  • Exponential Binary Search is useful for unbounded searches where size of array is infinite.
  • It works better than Binary Search for bounded arrays when the element to be searched is closer to the beginning of the array.