Searching Algorithms Questions Medium
Exponential search is a searching algorithm that is used to find a specific element in a sorted array. It is an improvement over binary search, especially when the size of the array is unknown or unbounded.
The algorithm works by first checking if the element to be searched is present at the first position of the array. If it is, the search is complete. Otherwise, it exponentially increases the range of the search by repeatedly doubling the index until it finds a range that includes the element or exceeds the array size.
Once the range is determined, a binary search is performed within that range to find the desired element. Binary search is a more efficient algorithm for searching within a smaller range.
The steps of the exponential search algorithm can be summarized as follows:
1. Start with an array of sorted elements and the element to be searched.
2. Check if the element is present at the first position of the array. If yes, the search is complete.
3. Determine the range for the binary search by doubling the index until it exceeds the array size or includes a value greater than the element being searched.
4. Perform a binary search within the determined range to find the desired element.
5. If the element is found, the search is complete. Otherwise, the element is not present in the array.
Exponential search has a time complexity of O(log n) for the binary search part and O(log i) for the exponential search part, where n is the size of the array and i is the index where the element is found. This makes it more efficient than a simple linear search but not as efficient as other advanced searching algorithms like interpolation search or hash-based searching.