Exponential Search Algorithm in C++

Introduction

Exponential search is an efficient searching algorithm that works on sorted arrays. It finds the range of the target value and then performs a binary search within that range. The algorithm is particularly useful for unbounded or infinite lists.

Program Structure

The program is structured into two main parts:

• Exponential Search Function: This function determines the range in which the target value may exist.
• Binary Search Function: This function performs a binary search within the identified range.

C++ Implementation

#include 
using namespace std;

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // Element not found
}

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

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

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

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10; // Element to be searched
    int result = exponentialSearch(arr, n, x);
    (result == -1) ? cout << "Element not found in array" 
                   : cout << "Element found at index " << result;
    return 0;
}

Explanation of the Code

1. **Binary Search Function**:

• This function takes the array, left and right indices, and the target value as parameters.
• It iteratively checks the mid-point of the specified range and narrows down the search area until it finds the target or exhausts the range.

2. **Exponential Search Function**:

• This function begins by checking if the target is the first element.
• It then identifies the range by doubling the index until it exceeds the size of the array or finds an element greater than the target.
• Finally, it calls the binary search function to locate the target within the determined range.

3. **Main Function**:

• It initializes an array and defines the target value.
• The result of the search is displayed, indicating whether the element was found and its index.

Conclusion

The exponential search algorithm is efficient for searching in sorted arrays, especially in cases where the size of the array is large and potentially unbounded. By combining exponential search with binary search, we can achieve optimal performance.