Interpolation Search in C++

Interpolation Search algorithm is used to search for a value in an ordered, uniformly distributed array of elements. Interpolation Search will go to different locations to start with, depending if the searched value is closer to the end or the start of the array, unlike Binary Search that is always looking for the middle. So, this technique is trying to find the exact location of the value, not the middle, using the interpolation formula. The search time is reduced, since it tries to find the best approximation of the position every time.

// Interpolation Search
#include <iostream>

int InterpolationSearch(int arrayOfNumbers[], int numberOfElements, int searchForNumber)
{
	// We are searching for values between indexes left and right
	int left = 0;
    int right = numberOfElements - 1;
    int estimatedMiddle = 0;

	while (arrayOfNumbers[right] != arrayOfNumbers[left] && searchForNumber >= arrayOfNumbers[left] && searchForNumber <= arrayOfNumbers[right])
	{
		// We estimate the middle index
		estimatedMiddle = left + ((searchForNumber - arrayOfNumbers[left]) * (right - left) / (arrayOfNumbers[right] - arrayOfNumbers[left]));

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


		// If the value is smaller than the one from the middle, we look only at the left part of the array
		else if (searchForNumber < arrayOfNumbers[estimatedMiddle])
        {
            right = estimatedMiddle - 1;
        }

		// If the value is greater than the one from the middle, we look only at the right part of the array
		else
			left = estimatedMiddle + 1;
	}

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

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

int main(void)
{
	int arrayOfNumbers[] = {1, 3, 5, 6, 8, 10, 11, 14};
	int searchForNumber = 11;

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