Interpolation search

Interpolation search is an improvement of the binary search algorithm in picking the middle index. Instead of always picking the middle element to be checked to a searched value like in a binary search, the middle index is not always at the middle position in an interpolation search. The algorithm will calculate the middle index based on the searched value, and pick the nearest element from the searched value. Similar to the binary search, in the interpolation search we have to pass an array we want to search and define the lowest index and the highest index, then calculate the middle index using the following formula:

Developing interpolation search algorithm

Let's borrow the array we used in the binary search algorithm, which is {3, 8, 11, 15, 16, 23, 28, 30, 32, 39, 42, 44, 47, 48, 50}, and find value 16. As we discussed earlier, in binary search, we've got 30, 15, and 23 as the middle index when it runs recursively, before we find the position of 16 (which means it...