 Caută
• oanaunciuleanu

# 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
{
return -1;
}
}

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

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

3 afișare

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.