# Interpolation search

#### Worst Case: n

Interpolation search is an improvement of Bianry Search as it begins the search near the higher end of the array or lower end depending on the element it is searching for. Binary search on the other hand always searches in the middle of the array.

The following example implements a small function that uses interpolation search in an already sorted array.

## C++/C example

```
//Function used to find the element in an sorted array
int InterSearch(int A[], int low, int high, int x) {

//the array us sorted therefore the element will be within this range
while (low <= high && x >= A[low] && x <= A[high])
{
//Get the current position using the formula to search nearer to high or nearer to low depending on element
int pos = low + (((double)(high - low) / (A[high] - A[low])) * (x - A[low]));

//if the element is found return it
if (A[pos] == x)
{
return pos;
}

//If the element is larger than the higher part of the array
if (A[pos] == x)
{
low = pos + 1;
}
//If the element is smaller than the lower part of the array
else {
high = pos - 1;
}
}
return -1;
}

int main() {

int A[] = { 0, 2, 5, 6, 7, 8, 9, 10, 11, 12 };
int x = 9;
int size = sizeof(A) / sizeof(A);

int location = InterSearch(A, 0, size - 1, x);

if (location == -1) {