What is interpolation Search?


What is interpolation search?


Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.

Binary search has advantage of time complexity over linear search. Linear search has worst-case complexity of Ο(n) whereas binary search has Ο(log n).


Interpolation search is an improved varient of binary search.this search algorithm works on probing position of required value.for this algorithm to work properly,the data collection should be in a sorted form and equally distributed
In interpolation search finds a particular item by computing the probe position,the probe position is a related to front part of the collection
1 2 3 4 5 6 7 8 9 10
1 2
If match occurs then index of item is returned .to split the list into two parts we use following method

Mid=lo+((hi -lo)/(A[hi]-A[lo])*(x-A[lo])

A: list
Lo: lowest index of list
Hi:highest index of list
A[n]:value sorted at index n in the list

Runtime complexity of interpolation search algorithm is 0(log(log n)) as compared to 0(log n) of BST in favourable situations

Steps to search the target data value index using position

1.start searching data from middle of list
2.if it is a match ,return index of item and exit
3.if it is not a match probe position
4.divide list using probe formula and find new middle
5.if data is greater than middle search is higher sub list
6.if data is smaller than middle then search is lower sub list
7.repeat until match