Exponential Search
A search algorithm particularly useful for unbounded or infinite arrays. It finds the range where the target element exists by exponentially increasing the index, then performs binary search within that range.
Visualization
Details
Analogy
Imagine looking for a word in a dictionary, but you don't know how many pages it has. Instead of checking page by page (linear) or guessing the middle (binary), you check page 1, then 2, then 4, then 8, then 16, doubling each time until you overshoot. Once you overshoot, you know the word is between your last two positions, and you can use binary search in that range.
Purpose
To efficiently search in sorted arrays, especially when the target is closer to the beginning. It combines the benefits of linear search for small ranges with binary search for larger ranges, making it ideal for unbounded arrays where the size is not known.
Use Cases
Ideal for searching unbounded or infinite lists where the size is unknown. Useful when the target element is likely to be near the beginning of the array. Common in database systems for range queries. Used in network protocols for timeout calculations. Effective when binary search overhead is too high for small datasets.
Algorithm Steps
function exponentialSearch(array, target):
if array[0] == target:
return 0
i = 1
while i < length(array) and array[i] <= target:
i = i * 2
return binarySearch(array, target, i/2, min(i, length-1))
Explanation
What's Happening?
Initial sorted array: [2, 3, 4, 10, 40, 50, 60, 70, 80, 90]. Starting exponential search with range [0, 9].
Code Implementation
def exponential_search(arr, target):
if arr[0] == target:
return 0
i = 1
while i < len(arr) and arr[i] <= target:
i = i * 2
# Binary search in the range
left = i // 2
right = min(i, len(arr) - 1)
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