Interpolation Search | Sorting and Searching | C++ Solution
Interpolation Search, is a Sorting and Searching related problem and in this post we will see how we can solve this challenge in C++
Interpolation search for array Useful only when the array is uniformly distributed wit unique values the idea is to use the formula which takes us to the the position closer to the index of the key rather than always splitting the array into equal parts like in binary search. best case: O(loglogn) worst case: O(n)
Please check the main.cpp snippet for the solution.
This solution originally posted at: Github by @susantabiswas