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:

1. Given a sorted array of n data elements, we first determine the subrange in the original list where the desired search item may be present
2. 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 2ⁱ 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, we move the index to the next location. Therefore, we first find the first occurrence of an exponent i such that the value at index 2ⁱ is greater than the search value. Then, the 2ⁱ becomes the lower bound and 2ⁱ-1 becomes the upper bound for this range of data elements in which the search value will be present. The exponential search algorithm is defined as follows:

1. First, we check the first element A[0] with the search element.
2. Initialize the index position i=1.
3. We check two conditions: (1) if it is the end of the array or not (i.e. 2ⁱ < len(A)), and (2) if A[i] <= search_value). In the first condition, we check if we have searched the complete list, and we stop if we have reached the end of the list. In the second condition, we stop searching when we reach an element whose value is greater than the search value, because it means the desired element will be present before this index position (since the list is sorted).
4. If either of the above two conditions is true, we move to the next index position by incrementing i in powers of 2.
5. We stop when either of the two conditions of step 3 is satisfied.
6. We apply the binary search algorithm on the range 2ⁱ//2 to min (2ⁱ, len(A)).

Let’s take an example of a sorted array of elements A = {3, 5, 8, 10, 15, 26, 35, 45, 56, 80, 120, 125, 138} in which we want to search for the element 125.

We start with comparing the first element at index i = 0, i.e. A[0] with the search element. Since A[0] < search_value, we jump to the next location 2ⁱ with i = 0, since A[2⁰] < search_value, the condition is true, hence we jump to the next location with i = 1 i.e. A[22¹] < search_value. We again jump to the next location 2ⁱ with i = 2, since A[2²] < search_value, the condition is true. We iteratively jump to the next location until we complete searching the list or the search value is greater than the value at that location, i.e. A[2ⁱ] < len(A) or A[2ⁱ] <= search_value. Then we apply the binary search algorithm on the range of the subarray. The complete process for searching a given element in the sorted array using the exponential search algorithm is depicted in Figure 10.13:

Figure 10.13: Illustration of the exponential search algorithm

Now, let us discuss the implementation of the exponential search algorithm. Firstly, we implement the binary search algorithm, which we have already discussed in the previous section, but for the completeness of this algorithm it is given again as follows:

def binary_search_recursive(ordered_list, first_element_index, last_element_index, term):
    if (last_element_index < first_element_index):
        return None
    else:
        mid_point = first_element_index + ((last_element_index - first_element_index) // 2)
        if ordered_list[mid_point] > term:
            return binary_search_recursive (ordered_list, first_element_index, mid_point-1, term)
        elif ordered_list[mid_point] < term:
            return binary_search_recursive (ordered_list, mid_point+1, last_element_index, term)
        else:
            return mid_point

In the above code, given the ordered list of elements, it returns the index of the location where the given data element is found in the list. It returns None if the desired element is not found in the list. Next, we implement the exponential_search() method as follows:

def exponential_search(A, search_value):
    if (A[0] == search_value):
        return 0    
    index = 1
    while index < len(A) and A[index] < search_value:
        index *= 2       
    return binary_search_recursive(A, index // 2, min(index, len(A) - 1), search_value)

In the above code, firstly, we compare the first element A[0] with the search value. If it matches then the index position 0 is returned. If that does not match, we increase the index position to 2⁰, i.e. 1. We check A[1] < search_value. Since the condition is true, we jump to the next location 2¹, i.e. we compare A[2] < search_value. Since the condition is true, we move to the next location.

We iteratively increase the index position in the power of 2 until the stop condition is satisfied:

    while index < len(A) and A[index] < search_value:
        index *= 2

Finally, when the stopping criteria are met, we use the binary search algorithm to search for the desired search value within the subrange as follows:

    return binary_search_recursive(A, index // 2, min(index, len(A) - 1), search_value)

Finally, the exponential_search() method returns the index position if the search value is found in the given array; otherwise, None is returned.

print(exponential_search([1,2,3,4,5,6,7,8,9, 10, 11, 12, 34, 40], 34))

The output of the above code snippet is:

12

In the above output, we get index position 12 for the search item 34 in the given array.

The exponential search is useful for very large-sized arrays. This is better than binary search because instead of performing a binary search on the complete array, we find a subarray in which the element may be present and then apply binary search, so it reduces the number of comparisons.

The worst-case time complexity of exponential search is O(log₂i), where i is the index where the element to be searched is present. The exponential search algorithm can outperform binary search when the desired search element is present at the beginning of the array.

We can also use exponential search to search in bounded arrays. It can even out-perform binary search when the target is near the beginning of the array, since exponential search takes O(log(i)) time whereas the binary search takes O(logn) time, where n is the total number of elements. The best-case complexity of exponential search is O(1), when the element is present at the first location of the array.

Next, let us discuss how to decide which search algorithm we should choose for a given situation.