Question

Interpolation search performs better than binary search when?

(a) array has uniformly distributed values but is not sorted

(b) array is sorted and has uniform distribution of values

(c) array is sorted but the values are not uniformly distributed

(d) array is not sorted

This is one of most asked question in data structure and algorithms interview.

Answer 1

Right option is (b) array is sorted and has uniform distribution of values

For explanation: Interpolation search is an improvement over a binary search for the case when array is sorted and has uniformly distributed values. Binary search performs better when the values are not distributed uniformly.