Exponential Search
Find range where element is present, then perform Binary Search. Good for unbounded or infinite arrays.
Enter target and search
1function exponentialSearch(arr, x):
2 if arr[0] == x: return 0
3 i = 1
4 while i < n and arr[i] <= x:
5 i *= 2
6 return binarySearch(arr, i/2, min(i, n-1), x)
Complexity
TimeO(log i)
SpaceO(1)
Where i is the index of element.