C++ Data Structures and Algorithms

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 needs four invocation of BinarySearch() function). However, by using interpolation search, we just need two invocation of an interpolation search function. Let's prove it.

Imagine we use the BinarySearch() function, but just replace the middleIndex calculation with the formula in the preceding section. First, we pass the array and have lowIndex = 0, highIndex = 14, and val = 16 (since we ...