- oanaunciuleanu

# 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);
}