JIYIK CN >

Exponential search, also known as doubling search or finger search, is an algorithm created for searching elements in large arrays. It is a two-step process. First, the algorithm tries to find the range in which the target element exists (L，R), and then uses binary search within this range to find the exact location of the target.

It is named exponential search because it finds the holding element in a range by searching pow(2,k)which element in index has the first index kgreater than the target element. Despite its name, the time complexity of this algorithm is logarithmic. It is very useful when the array is infinite in size and converges to a solution much faster than binary search.

Index Search Algorithm

Suppose we have an unsorted array A[]containing nelements and we want to find an element X.

• Checks if the first element itself is the target element, ie A[0] == X.
• Initialize i to 1.
• When i < n and A[i] <= X, do the following.
  • Increment i by powers of 2, ie i=i*2.
• Perform a binary search in the range i/2 to min(i,n-1).

Index Search Example

Suppose we have an array: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), and we want to find X - 10.

1. Initialize i to 1.
2. A[1] = 2 < 10, so increment i to 2.
3. A[2] = 3 < 10, so increment i to 4.
4. A[4] = 5 < 10, so increment i to 8.
5. A[8] = 9 < 10, so increment i to 16.
6. i = 16 > n Therefore binary search is called in the range of i/2, i.e. 8 to min(i,n-1), i.e. min(16,10) =10.
7. Initialize lo to i/2 = 8 and hi to min(i,n-1) = 10.
8. The calculated mid is 9.
9. 10=10, that is, A[9] == X, so 9 is returned.

Implementation of the exponential search algorithm

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x)
{
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            lo = m + 1;
        else
            hi = m - 1;
    }
    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 - 1), x);
}

int main()
{
    int n = 11;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int x = 10;
    int result = exponentialSearch(arr, n, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

Exponential search algorithm complexity

Time Complexity

• Average situation

The average case time complexity is O(logi), where iis the index of the target element within the array X. It is even better than binary search when the element is close to the beginning of the array.

• Best Case

The best case occurs when the element we are comparing is the element we are searching for and is returned in the first iteration. The time complexity of the best case is O(1).

• Worst case scenario

The worst case time complexity is the same as the average case time complexity. The worst case time complexity is O(logi).

Space complexity

The space complexity of this algorithm is O(1), since it does not require any additional space except for the temporary variables.