Exponential search
Exponential search is another search algorithm that is mostly used when we have large numbers of elements in a list. Exponential search is also known as galloping search and doubling search. The exponential search algorithm works in the following two steps:
- Given a sorted array of
ndata elements, we first determine the subrange in the original list where the desired search item may be present - Next, we use the binary search algorithm to find out the search value within the subrange of data elements identified in step 1
Firstly, in order to find out the subrange of data elements, we start searching for the desired item in the given sorted array by jumping 2i elements every iteration. Here, i is the value of the index of the array. After each jump, we check if the search item is present between the last jump and the current jump. If the search item is present then we use the binary search algorithm within this subarray, and if it is not present...