5

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?

4
  • I don't think it exists. Where did you hear about it? It could just be a mistake. On second thought, it could be a scheme to switch to binary search if the interpolation search doesn't seem to be working, in order to avoid the O(n) worst case. That's just speculation, though. I haven't heard of it.
    – GregRos
    Mar 17, 2015 at 21:01
  • Where did this question come from? If it's homework, could you ask the professor? Mar 17, 2015 at 21:07
  • I am reading previous exams and this one is of 2002: Give an explanation of the Binary Interpolation Search (BIS). Give worst case complexity and average case complexity.
    – Oti Na Nai
    Mar 17, 2015 at 21:36
  • Did you try Google? Algorithms and Theory of Computation Handbook
    – dfeuer
    Mar 17, 2015 at 22:35

4 Answers 4

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.

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.

0

Binary interpolation search is a vary of interpolation search, but when the √n field that x exists in is found, we do binary search in it, instead of doing interpolation search again.

0

Binary interpolation search operates like interpolation search, with the difference that when we arrive to a point that the spaces between the numbers are very small , the search changes to binary.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.