Loading...
A specialized searching algorithm for unbounded or large sorted arrays. It exponentially finds a range where the target might exist and then uses binary search to pinpoint it.
Where i is target index
Constant extra space
Fast range finding
Unknown array sizes
def binary_search(arr, left, right, target):
"""Helper function for binary search"""
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def exponential_search(arr, target):
"""
Exponential Search Algorithm
Time Complexity: O(log n)
Space Complexity: O(1)
Prerequisite: Array must be sorted
"""
# Check if element is at first position
if arr[0] == target:
return 0
# Find range for binary search by repeated doubling
bound = 1
while bound < len(arr) and arr[bound] < target:
bound *= 2
# Perform binary search in found range
left = bound // 2
right = min(bound, len(arr) - 1)
return binary_search(arr, left, right, target)
# Example usage
sorted_array = [1, 2, 3, 4, 5, 8, 10, 15, 20, 26, 30, 31, 35, 42, 50, 65, 70, 88]
target = 42
result = exponential_search(sorted_array, target)
if result != -1:
print(f"Element {target} found at index {result}")
else:
print(f"Element {target} not found")Note: 'i' represents the index of the element being searched. This makes it particularly effective when elements are expected towards the beginning of large datasets.