I was reading about interpolation search at https://www.geeksforgeeks.org/interpolation-search when I come across this sentence "Let's assume that the elements of the array are linearly distributed." What linearly distributed means in the sentence?

CodePudding user response：

They mean "following an arithmetic progression" or approximately so. The idea is that smoothly varying data is predictable to some extent.

You can use this knowledge to speed-up the search by estimating where the target value could be located, from the knowledge of some values.

E.g. in the sorted sequence 14, 22, 31, 46, 55, 57, 70, 78, 91, 99, the value 31 is likely to be the 3rd element (inverse linear interpolation between 14 and 99 yields the index 2.8, which rounds to 3).

One could also say uniformly distributed. If the data is not so spread, interpolation search can be counter-productive.