What is a binary interpolation search?

Question

I understand what a binary search is, as well as an interpolation search.

I've got to answer a question that asks me to explain what a binary interpolation search (bis) is, all in one sentence. Isn't this though two different kind of searches, binary and interpolation? I have searched a lot and can't find this kind of search. What am I missing?

Answer 1

I'm not sure exactly what binary interpolatuion search performs, however, the binary interpolation sort had been applied in the insert sort. E,g., given a element, insert into a sorted array and keep its sort simultaneously. If we compare it with every emelemt directly to find the correct location to insert, the time complexity would be O(n), now that it's sorted, the binary search could be applied with this situation, with time complexity O(logn), as we all know.

Answer 2

Binary Interpolation Search is a variation of Interpolation Search by Perl and Reingold[77].

The main difference between IS and BIS is that in BIS we reduce the length of the interval to be searched from n to √n to complete search in O(loglogn).

You can find more detailed explanation here. http://www.sciencedirect.com/science/article/pii/0020019080901398

PS:CEID everywhere.