Exponential Search

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

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.

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.

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.