-
Book Overview & Buying
-
Table Of Contents
C++ Data Structures and Algorithms
By :
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 (2n). 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.
Let's use the array we used in jump search, {8, 15, 23, 28, 32, 39, 42, 44, 47, 48}, to perform an exponential search, and we will also find value 39. First, we apply setblockIndex = 1, then compare array[1] with the searched value, 39. Since 15 is lower than 39, the algorithm sets blockIndex = 2. array[2] is still lower than 39, then moves to array[4]....