Introduction

Exponential search is an algorithm for searching a sorted array. It works by
first finding a range where the target element may reside. It does this by
exponentially increasing the index until it exceeds the size of the array,
and then performs a binary search within that range.

Program Structure

• Function exponentialSearch: This function
  implements the exponential search logic.
• Function binarySearch: A helper function
  that performs binary search on a given range.
• Main Function: This is where the program execution begins.
  It initializes the array and calls the exponentialSearch function.

Code

#include 

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if x is present at mid
        if (arr[mid] == x)
            return mid;

        // If x is greater, ignore left half
        if (arr[mid] < x)
            left = mid + 1;
        else // If x is smaller, ignore right half
            right = mid - 1;
    }
    return -1; // Element is not present
}

// Function to perform exponential search
int exponentialSearch(int arr[], int n, int x) {
    // If x is present at the first location
    if (arr[0] == x) return 0;

    // Find range for binary search
    int i = 1;
    while (i < n && arr[i] <= x) {
        i = i * 2;
    }

    // Call binary search for the found range
    return binarySearch(arr, i / 2, (i < n ? i : n - 1), x);
}

// Main function
int main() {
    int arr[] = {2, 3, 4, 10, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10; // Element to search for

    int result = exponentialSearch(arr, n, x);
    if (result == -1)
        printf("Element is not present in the array\n");
    else
        printf("Element found at index: %d\n", result);
    
    return 0;
}

Explanation of the Code

The program consists of two main functions: binarySearch and
exponentialSearch.

• binarySearch: This function takes an array, two indices
  (left and right), and the element to search for. It repeatedly divides
  the search range in half until it finds the target element or exhausts
  the search range.
• exponentialSearch: This function first checks if the
  element is at the first position. If not, it doubles the index until it
  goes out of bounds or the element at that index is greater than the
  target. It then calls binarySearch to find the element
  within the determined range.

Conclusion

The exponential search algorithm is efficient for unbounded or infinite
lists. It has a time complexity of O(log i) for searching within the
determined range, making it faster than a linear search for larger arrays.