Exponential Search Algorithm

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Algorithm
Complexity
Implementations
Applications
Discussions

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


#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.