Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

Data Structures - Exponential Search Algorithm

Posted on Edited on In Disqus:

Basic programming - Exponential Search

Question:

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

Example:

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

Source code:

Version 1

Idea:
Based on the iterative approach of binary search, we can use recursive function to implement it easily at 7 - 19 line.

Exponential search is similar with binary search, use the exponential of 2 as the search range is only different part at first.
The detailed demonstration is shown as below:

Let explain how to implement exponential search, it involves two steps:
1. Find the range where element is possible exist. 2. Do binary search in above found range.

At 22 line, index 0 of array should be checked if value is equal to target.
At 24 line, delcare integer variable as searchIndex (range), it initialized to 1.
At 25 line, searchIndex variable is the exponential growth based on 2. so the index range will be 1, 2, 4, 8, 16 ... etc. If arr[searchIndex] < target, it means the target may be exist between arr[searchIndex/2] and arr[searchIndex].

There will be an expected cases that is searchIndex is bigger than the lenght of array, so the tail index is from min(searchIndex, n) before calling binarySearch(). P.S. n is index at the end of array and head index is searchIndex/2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int binarySearch(vector<int> arr, int target, int head, int tail){
    if(head <= tail){
        int middle = (head + tail) / 2;
        if(arr[middle]== target) return middle;
        
        if(arr[middle] > target){
            return binarySearch(arr, target, head, middle - 1);
        }else{
            return binarySearch(arr, target, middle + 1, tail);
        }
    }
    return -1;
};

int exponentialSearch(vector<int> arr, int target){
    if(arr[0] == target) return 0;
    const int n = arr.size() - 1;
    int searchIndex = 1;
    while(searchIndex < n && arr[searchIndex] < target) searchIndex*= 2;
    return binarySearch(arr, target, searchIndex/2, min(searchIndex, n));
};

int main()
{
    vector<int> arr{2, 3, 4, 10, 40};
    int x = 40;
    int res = exponentialSearch(arr, x);
    (res == -1)?cout << "Input is not exist in array":cout << "Index " << res << " is " << arr[res];

    return 0;
}