Interpolation search is a searching algorithm that applies to a sorted & equally distributed array, and it is an improved variant of binary search . Like binary search, it uses the divide and conquer algorithm but 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, the interpolation search considers the searched element and, based on an algorithm, checks for those locations for which the value of the element is 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)
return "not found"
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;
return "Not Found"
arr = [10, 20, 40, 77, 86, 89, 91]
print(Interpolation_Search(arr, 86))
Output:
86 is at 4 index
Conclusion
With this, we are concluding our tutorial on interpolation search. This search is highly helpful in applications in various real-life scenarios where efficient data retrieval is crucial, like weather forecasting, database systems, library catalogs, and more. Overall, interpolation search plays a vital role in locating specific data points within vast datasets rapidly.
We hope that this information proves helpful to you. In case of any queries, please let us know in the comment section below.
Good luck!
People are also reading: