Exponential search is an algorithm used for searching sorted, unbounded/infinite arrays. The idea is to determine a range that the target value resides in and perform a Binary Search within that range. Assuming that the array is sorted in ascending order, it looks for the first exponent k, where the value 2k is greater than the search key. Now 2k and 2k-1 becomes the upper bound and lower bound for the binary search algorithm respectively.
- Time Complexity: O(Log n)
- Auxiliary Space: The above implementation of Binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space.
Applications of Exponential Search:
Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite. Please refer Unbounded Binary Search for an example.
It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
Exponential search involves two steps:
- Find range where element is present
- Do Binary Search in above found range
How to find the range where element may be present?
The idea is to start with subarray size 1, compare its last element with x, then try size 2, then 4 and so on until last element of a subarray is not greater.
CODE
# To find an element x in a sorted array using Exponential Search
# A recurssive 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 = int(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
# occurence 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), 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 thye array")
else:
print ("Element is present at index %d" %(result) )
Output: Element is present at index 3
Python, Data structures, OOPS, Big O 
One thought on “Exponential Search”