C++ Data Structures and Algorithms

Exponential search

Exponential search is similar to a jump search, since it also divides the input array into several subarrays; however, in exponential search, the step we jump is increased exponentially (2ⁿ). In exponential search, we initially compare the second index (blockIndex = 1), then compare array[1] with the searched value. If the array[1] is still lower than the searched value, we increase the blockIndex exponentially to become 2, 4, 8, and so on, until the array[blockIndex] is higher than the searched value. Then we can perform the binary search to the subarray defined by the blockIndex.