# Data Structure & Algorithm: Interpolation Search

By | January 12, 2020 Interpolation search is a searching algorithm that applies on a sorted & equally distributed array, and it is an Improved variant of Binary Search. Like binary search, it uses the divide and conquers algorithm, but unlikely, it does not divide the array into two equal parts to search the element. As compared to a linear search, binary search is more efficient, but the Interpolation search is more effective than any other searching algorithm.

With Binary searching, if we want to locate the position of an element in the array, we require O(log n) time complexity, but we have another searching algorithm that is capable of searching an element with O(log log n) time complexity.

As binary search always checks for the middle index, rather than considering the element, but the interpolation search, consider the searched element and based on an algorithm check for those locations for which the value of element being searched.

### Time Complexity

 Linear Search Binary Search Interpolation Search O(n) O(log n) O(log log n)

### Algorithm

• The array must be sorted
• Make a start =0 and end = n-1
• Use a formula to locate the position, which brings us near to the searched element
`pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))`
• If arr[pos] == target return the pos
• If target > arr[pos] start = pos+1
• Else end = pos-1

### Pseudocode

```start =0
end = len(arr) -1
found = false
while found == false and start <=end
{
pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))
if arr[pos]==target
{
return pos
}
if target > arr[pos]
{
start = pos+1
}
else
{
end = pos-1
}
}```

## Implementation

### Python:

```def Interpolation_Search (arr,target):
start = 0
end = len(arr)-1
found = False

while start <= end and found == False:
if start == end:
if arr[start] == target:
return "{} is at {} index".format(target,pos)

pos = start + (((end-start)//(arr[end]-arr[start])) * (target-arr[start]))

if arr[pos] == target:
return "{} is at {} index".format(target,pos)

if arr[pos] < target:
start = pos + 1;
else:
end = pos - 1;

`86 is at 4 index`