Interpolation Search is an enhanced variant of binary search, optimized for uniformly distributed sorted arrays. It smartly estimates the target’s position using linear interpolation.
Estimates target position based on value distribution
Can perform extremely well on uniformly distributed data
Performance degrades with non-uniform data
Sensitive to the distribution of data. Best results when the data is uniformly distributed.