The interpolation search algorithm is an improved variation of the binary search. While the binary search always checks the value in the mid position, the interpolation search might check different places of the array depending on the value that is being searched.
To make the algorithm work, the data structure needs to be sorted first. These are the steps that the algorithm follows:
- A value is selected using the position formula
- If the value is the one we are looking for, we are done (the value was found)
- If the value we are looking for is lesser than the selected one, then we will go back to step 1 using the left subarray (lower)
- If the value we are looking for is bigger than the selected one, then we will go back ...
