Exponential Search in C++

Exponential search is an algorithm used for finding a value in an array. The array must be ordered. This algorithm is based on the Binary Search Algorithm. This search jumps 2^I elements at every iteration. I is the value of loop control variable, and it verifies if the search element is between the last and the current jumps.

This algorithm, also known as doubling search, galloping search, Struzik search is used for searching sorted, unbounded (infinite) lists.

To explain it in a simpler way, we have to start with a sub-array of size 1, compare its last element with the searched value, and then double the size to 2, and then to 4, until the last element of the sub-array is not greater. In this way, the searched value must be between i/2 and I, this is because in the previous iteration we couldn’t find a greater value.

// Exponential Search

#include <iostream>
using namespace std;

int binarySearch(int arrayOfNumbers[], int searchForNumber, int left, int right)
{
	if (right >= left)
	{
		int middle = left + (right - left) / 2;

		if (arrayOfNumbers[middle] == searchForNumber)
        {
            printf("The number %d is found at index %d", searchForNumber, middle);
            return middle;
        }

		if (arrayOfNumbers[middle] > searchForNumber)
        {
            return binarySearch(arrayOfNumbers, searchForNumber, left, middle - 1);
        }
		return binarySearch(arrayOfNumbers, searchForNumber, middle + 1, right);
	}

	printf("The number %d was not found in the array", searchForNumber);
	return -1;
}

int exponentialSearch(int arrayOfNumbers[], int numberOfElements, int searchForNumber)
{
    // Check if the desired number is on first position
    if (arrayOfNumbers[0] == searchForNumber)
        return 0;
    //ad a variable i for the jump
    int i = 1;
    while (i < numberOfElements && arrayOfNumbers[i] <= searchForNumber)
        {
            // multiply i each iteration
            i = i*2;
        }
    // apply binary search in the interval where the value is between i/2 and i
    return binarySearch(arrayOfNumbers, searchForNumber, 0, numberOfElements - 1);
}

int main(void)
{
	int arrayOfNumbers[] = {1, 4, 9, 15, 22, 25, 38, 42, 77, 85};
	int searchForNumber = 77;

	int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
	int result = exponentialSearch(arrayOfNumbers, numberOfElements, searchForNumber);
}