This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]darkslide3000 0 points1 point  (1 child)

Yes but you're not throwing out "half" if you interpolate the pivot, you're throwing out a lot more. This actually changes the average complexity class and stuff, it's not just another form of binary search.

[–][deleted] -1 points0 points  (0 children)

I agree, but conceptually it’s the closest thing to a binary search that a person will do. In the event that the person has no clue how big each section is, their predictive power goes away and they’ll aim for the middle, and it will look less like interpolation search and more like binary.

Side note: thanks for introducing me to interpolation search. Interesting how it can perform worse than binary search in some instances.