Exponential Search

The name of this searching algorithm may be misleading as it works in O(Log n) time. The name comes from the way it searches an element.

Given a sorted array an element x to be searched, find position of x in the array:

Input: arr[ ] = {10, 20, 40, 45, 55} x = 45

Output: Element found at index 3

Input: arr[ ] = {10, 15, 25, 45, 55} x = 15

Output: Element found at index 1

Exponential search involves two steps:

1. Find range where element is present
2. Do Binary Search in above found range.

[ad type=”banner”]

How to find the range where element may be present?

The idea is to start with sub-array size 1 compare its last element with x, then try size 2, then 4 and so on until last element of a sub-array is not greater.
Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i (Why i/2? because we could not find a greater value in previous iteration)

C++ Implementation:

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20an%20element%20x%20in%20a%0A%2F%2F%20sorted%20array%20using%20Exponential%20search.%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%2C%20int%2C%20int)%3B%0A%20%0A%2F%2F%20Returns%20position%20of%20first%20ocurrence%20of%0A%2F%2F%20x%20in%20array%0Aint%20exponentialSearch(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%7B%0A%20%20%20%20%2F%2F%20If%20x%20is%20present%20at%20firt%20location%20itself%0A%20%20%20%20if%20(arr%5B0%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Find%20range%20for%20binary%20search%20by%0A%20%20%20%20%2F%2F%20repeated%20doubling%0A%20%20%20%20int%20i%20%3D%201%3B%0A%20%20%20%20while%20(i%20%3C%20n%20%26%26%20arr%5Bi%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20i%20%3D%20i*2%3B%0A%20%0A%20%20%20%20%2F%2F%20%20Call%20binary%20search%20for%20the%20found%20range.%0A%20%20%20%20return%20binarySearch(arr%2C%20i%2F2%2C%20min(i%2C%20n)%2C%20x)%3B%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20binary%20search%20function.%20It%20returns%0A%2F%2F%20location%20of%20x%20in%20%20given%20array%20arr%5Bl..r%5D%20is%0A%2F%2F%20present%2C%20otherwise%20-1%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20x)%0A%7B%0A%20%20%20%20if%20(r%20%3E%3D%20l)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20mid%20%3D%20l%20%2B%20(r%20-%20l)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20element%20is%20present%20at%20the%20middle%0A%20%20%20%20%20%20%20%20%2F%2F%20itself%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20mid%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20smaller%20than%20mid%2C%20then%20it%0A%20%20%20%20%20%20%20%20%2F%2F%20can%20only%20be%20present%20n%20left%20subarray%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3E%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20l%2C%20mid-1%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20the%20element%20can%20only%20be%20present%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20right%20subarray%0A%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20mid%2B1%2C%20r%2C%20x)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%0A%20%20%20%20%2F%2F%20in%20array%0A%20%20%20%20return%20-1%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main(void)%0A%7B%0A%20%20%20int%20arr%5B%5D%20%3D%20%7B2%2C%203%2C%204%2C%2010%2C%2040%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2F%20sizeof(arr%5B0%5D)%3B%0A%20%20%20int%20x%20%3D%2010%3B%0A%20%20%20int%20result%20%3D%20exponentialSearch(arr%2C%20n%2C%20x)%3B%0A%20%20%20(result%20%3D%3D%20-1)%3F%20printf(%22Element%20is%20not%20present%20in%20array%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3A%20printf(%22Element%20is%20present%20at%20index%20%25d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result)%3B%0A%20%20%20return%200%3B%0A%7D” message=”c++” highlight=”” provider=”manual”/]

Output :

[pastacode lang=”cpp” manual=”Element%20is%20present%20at%20index%203″ message=”” highlight=”” provider=”manual”/]

Time Complexity : O(Log n)
Auxiliary Space : The above implementation of Binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space.

Applications of Exponential Search:

1. Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite. Please refer Unbounded Binary Search for an example.
2. It works better than Binary Search for bounded arrays also when the element to be searched is closer to the first element.

[ad type=”banner”]