Exponential Searching Algorithm | 100 Days DSA Mastery Course Day-14

Exponential Search is a searching algorithm that works by repeatedly doubling the search interval until the target value is found or the interval becomes too large. It's particularly efficient for large sorted arrays where the target value is likely to be found towards the end of the array.

Steps:

Find the smallest power of 2 greater than or equal to the array's length.
Start with a search interval from 1 to 2^i.
Compare the target value with the element at the index 2^i.
If the target value is greater than the element at 2^i, update the search interval to from 2^i + 1 to 2^(i+1).
If the target value is less than or equal to the element at 2^i, perform binary search within the interval from 1 to 2^i.
Time Complexity:

Best case: O(1) (if the target value is found in the first jump)
Average case: O(log n)
Worst case: O(log n)
Space Complexity:

O(1)
Advantages:

Efficient for large sorted arrays where the target value is likely to be found towards the end of the array.
Simple to implement.
Disadvantages:

Requires a sorted array.
Not as efficient as binary search for smaller arrays or when the target value is not towards the end of the array.
In conclusion, exponential search is a useful optimization over linear search for large sorted arrays with target values towards the end. It combines the advantages of both linear and binary search, providing efficient search performance in such scenarios.