Geek Answers Handbook

What is binary interpolation search?

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

I have to answer a question that asks me to explain what binary search for interpolation (bis) is all in one sentence. Aren't these two different kinds of searches, binary and interpolation? I searched a lot and can not find such a search. What am I missing?

+4
source share
2 answers

I’m not sure what exactly performs binary interpolation searches, however binary interpolation sort has been applied in insert sort. E, g., Given by the element, insert into the sorted array and save its sorting at the same time. If we compare it with each emelemt directly to find the correct location for the insert, then the time complexity will be O (n), now that it is sorted, binary search can be applied with this situation with the time complexity O (logn), since we we all know.

+1
source

The binary interpolation search is a variant of the interpolation search of Perl and Reingold [77].

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

. http://www.sciencedirect.com/science/article/pii/0020019080901398

PS: CEID .

0

More articles:


All Articles