Interpolation Search is an improvement over Binary Search for uniformly distributed sorted arrays. Instead of always probing the midpoint, it estimates where the target likely is using a linear interpolation formula. For uniform distributions it achieves O(log log n) average case — dramatically faster than Binary Search.
int interpolationSearch(vector<int>& arr, int target) {
int lo = 0, hi = arr.size()-1;
while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
if (lo == hi) return arr[lo]==target ? lo : -1;
int pos = lo + ((double)(target-arr[lo])/(arr[hi]-arr[lo]))*(hi-lo);
if (arr[pos]==target) return pos;
if (arr[pos]<target) lo=pos+1; else hi=pos-1;
}
return -1;
}Instead of picking the midpoint, Interpolation Search estimates pos = lo + ((target - arr[lo]) / (arr[hi] - arr[lo])) * (hi - lo). For uniform data this places the probe very close to the target.
For uniformly distributed data, Interpolation Search reduces comparisons to O(log log n). For 1 billion elements, Binary Search needs ~30 comparisons; Interpolation Search needs ~5.
For non-uniform data (e.g., exponential distribution), the probe can be far from the target every time, giving O(n) worst case. Always consider data distribution before choosing this over Binary Search.
Quiz coming soon for this algorithm.