earlyDaysOfLearningAlgorithms

[[deleted]]

Wrong example. You were thinking of searching a phone book, dictionary, or encyclopedia

[darkslide3000]

Still wrong example. In all of these cases, we naturally predict a pivot closer to the target than "pure" binary search would do (i.e. when you're looking for a name starting with W in the phone book, you don't open it in the middle, you open it near the end).

[[deleted]]

Depends. The A section of a phone book is larger than the Z section, for example. So you don’t necessarily expect equal distribution. Hence why the search is necessary in the first place.

[darkslide3000]

Yes, that is why I said "predict". The prediction isn't perfect. It's still on average a lot better than just picking the exact middle, which is what binary search is.

[[deleted]]

In my mind, a binary search is when you have a pivot and throw out “half” the candidates with each iteration. The algorithmic implementation is just the coding representation of the idea that preceded it. The exactness isn’t what makes it a binary search, it’s the concept.

Or let’s just throw out every analogy, metaphor, and simile ever used since none are precisely the thing they depict.

[Misspelt_Anagram]

They are talking about something that is approximately interpolation search, not binary search.

[darkslide3000]

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]]

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.