Exponential Search

  1. Exponential Search Algorithm
  2. Exponential Search Example
  3. Exponential Search Algorithm Implementation
  4. Exponential Search Algorithm Complexity
Note

If you don’t know what is binary search, then first please go through the binary search algorithm here.

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

It is named exponential search because it finds the range holding element by searching for the first exponent k for which element at index pow(2,k) is greater than the target. Although its name is exponential search, the time complexity of this algorithm is logarithmic. It is very useful when arrays are of infinite size and converges to a solution much faster than binary search.

Exponential Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

  • Check if the first element itself is the target element i.e. A[0] == X.
  • Initialize i as 1.
  • While i < n and A[i] <= X do the following:
    • Increment i in powers of 2 i.e. i = i*2.
  • Apply binary search on the range i/2 to min(i,n-1).

Exponential Search Example

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

  • Initialize i as 1
  • A[1] = 2 < 10 so increment i to 2.
  • A[2] = 3 < 10 so increment i to 4.
  • A[4] = 5 < 10 so increment i to 8.
  • A[8] = 9 < 10 so increment i to 16.
  • i = 16 > n Hence call binary search on the range i/2 i.e. 8 to min(i,n-1) i.e. min(16,10) =10
  • Initialize lo as i/2 = 8 and hi as min(i,n-1) = 10.
  • calculate mid as 9.
  • 10 == 10 i.e. A[9] == X ,hence return 9.

Exponential Search Algorithm Implementation

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

The average-case time complexity is O(logi) where i is the index of target element X inside the array. It even outperforms binary search when the element is near the beginning of the array.

  • Best Case

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

  • Worst-Case

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

Space Complexity

This algorithm’s space complexity is O(1) because it doesn’t require any extra space other than temporary variables.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Search Algorithm

  • Interpolation Search
  • Jump Search