# Interpolation Search

- Interpolation Search Algorithm
- Interpolation Search Example
- Interpolation Search Algorithm Implementation
- Interpolation Search Algorithm Complexity

Interpolation search is a fast and efficient searching algorithm. It improves the binary search algorithm for scenarios where array elements are uniformly distributed over the sorted array. It works on the probing position of the required value. Unlike binary search, it does not always go to the middle of the array but may go to any position depending on the value of the key to be searched. We compare the value at the estimated position and reduce the search space to the part after or before it. For example, when we search a word in the dictionary, we flip pages according to the position of letters inside it and not by splitting search space into two halves every time.

## Interpolation Search Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements and we want to find a given element `X`

.

##### Set

`lo`

as`0`

,`mid`

as`-1`

and`hi`

as`n-1`

.##### While

`lo`

<=`hi`

and X lies in the range between lo and hi, i.e.`X >= A[lo]`

and`X <= A[hi]`

.- Calculate
`mid`

by using the formula for probe position -`mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])`

- If the element at probe position is less than target element move to right. If
`A[mid]`

<`X`

set`lo`

as`mid + 1`

. - Else if the element is greater than the target element then move to left. If
`A[mid]`

>`X`

, set`hi`

as`mid-1`

. - Else we have found the element and return
`mid`

- Calculate
##### If

`lo`

==`hi`

, only one element is remaining check if it is the target element i.e. if`A[lo]`

==`X`

.- If
`true`

, then return`lo`

. - Else return
`-1`

.

- If

## Interpolation Search Example

Suppose we have the array: `(1, 3, 7, 8, 11, 15, 17, 18, 21)`

, and we want to find X - `18`

.

##### Set

`lo`

=`0`

,`mid`

=`-1`

and`hi`

=`8`

.##### Calculate

`mid`

as`6`

by using the formula -`0 + (18 - 1)*(8 - 0)/(21-1)`

.##### Then we compare

`A[6]`

with`X`

to see it is smaller and set`lo`

as`7`

.##### Calculate

`mid`

using`7 + (18 - 18)*(8 - 7)/(21 - 18)`

.##### Then we compare

`A[7]`

with`X`

to see it is equal to`18`

and return the index`7`

.

## Interpolation Search Algorithm Implementation

```
#include <bits/stdc++.h>
using namespace std;
int interpolation_search(int arr[], int n, int X)
{
int lo = 0;
int hi = n - 1;
int mid;
while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
if (arr[mid] < X)
lo = mid + 1;
else if (X < arr[mid])
hi = mid - 1;
else
return mid;
}
if (X == arr[lo])
return lo ;
else
return -1;
}
int main(void)
{
int n = 9;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 4;
int result = interpolation_search(arr, n, x);
if (result == -1) {
cout << "Element not found !!";
}
else cout << "Element found at index " << result;
return 0;
}
```

## Interpolation Search Algorithm Complexity

### Time Complexity

- Average Case

The algorithm’s average-case time complexity is of the order of `O(log(logn))`

. It happens when all the elements inside the array are uniformly distributed.

- Best Case

The best-case occurs when the element we are searching for is the first element probed by interpolation search. The best-case time complexity of the algorithm is `O(1)`

.

- Worst-Case

The worst-case occurs when the numerical values of the targets increase exponentially. The worst-case time complexity of the algorithm is `O(n)`

.

### Space Complexity

This algorithm’s space complexity is `O(1)`

because it doesn’t require any data structure other than temporary variables.