Exponential Searchan exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list
The name of this searching algorithm may be misleading as it works in O(Log n) time. The name comes from the way it searches an element.
Exponential search involves two steps
1. Find range where element is present
2. Do Binary Search in above found range.
Example :Given a sorted array, and an element x to be
searched, find position of x in the array.
Input: arr[] = {10, 20, 40, 45, 55}
x = 45
Output: Element found at index 3
Input: arr[] = {10, 15, 25, 45, 55}
x = 15
Output: Element found at index 1
Below are the implementation of Exponential Search into programs
// C++ program to find an element x in a
// sorted array using Exponential search.
#include
#include
#include
#define min
int binarySearch(int arr[], int, int, int);
// Returns position of first occurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
// If x is present at first location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return binarySearch(arr, i/2,
min(i, n-1), x);
}
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
// can only be present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
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;
}
Code
// Java program to
// find an element x in a
// sorted array using
// Exponential search.
import java.util.Arrays;
class GFG
{
// Returns position of
// first occurrence of
// x in array
static int exponentialSearch(int arr[],
int n, int x)
{
// If x is present at first location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return Arrays.binarySearch(arr, i/2,
Math.min(i, n-1), x);
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr,
arr.length, x);
System.out.println((result < 0) ?
"Element is not present in array" :
"Element is present at index " +
result);
}
}
Code
Python program to find an element x
# in a sorted array using Exponential Search
# A recursive binary search function returns
# location of x in given array arr[l..r] is
# present, otherwise -1
def binarySearch( arr, l, r, x):
if r >= l:
mid = l + ( r-l ) // 2
# If the element is present at
# the middle itself
if arr[mid] == x:
return mid
# If the element is smaller than mid,
# then it can only be present in the
# left subarray
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)
# Else he element can only be
# present in the right
return binarySearch(arr, mid + 1, r, x)
# We reach here if the element is not present
return -1
# Returns the position of first
# occurrence of x in array
def exponentialSearch(arr, n, x):
# IF x is present at first
# location itself
if arr[0] == x:
return 0
# Find range for binary search
# j by repeated doubling
i = 1
while i < n and arr[i] <= x:
i = i * 2
# Call binary search for the found range
return binarySearch( arr, i // 2,
min(i, n-1), x)
# Driver Code
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponentialSearch(arr, n, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
Code