exponential search Algorithm
The exponential search algorithm, also known as an exponential binary search, is an advanced searching technique that efficiently finds the position of a target value within a sorted array. The primary advantage of this algorithm is its ability to rapidly narrow down the search range by repeatedly doubling the size of the search interval, making it particularly suitable for large datasets. This algorithm consists of two main phases: first, it identifies an appropriate range containing the target value, and second, it uses binary search to find the exact position of the target within the identified range.
In the initial phase, the algorithm starts at the first element of the array and keeps doubling the index until it either finds the target value or the value at the current index is larger than the target value. This process continues until the bounds of the search range are established. Once the range is determined, the second phase of the algorithm begins, where the binary search technique is employed to locate the target value within the identified range. Binary search works by repeatedly dividing the search interval in half and comparing the middle element with the target value, thus narrowing down the search range until the target value is found or the search interval becomes empty. The combination of these two phases allows exponential search to be more efficient than both linear search and binary search when searching for a target value in large, sorted arrays.
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int, int, int);
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), x);
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
