Hacker News Reader

Comment by beeforpork | Hacker News Reader

Yes, exactly, binary search is full of traps. And you may have missed one:

  (left + right) // 2

is better written 'left + ((right - left) // 2)'. At least on some languages, I don't know which type Python will use there.

'Nearly All Binary Searches and Mergesorts are Broken':

https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

View on HN

It could potentially be a pretty good interview question to weed out those who have spent the last 6 months memorizing algorithms.

Realistically, anyone with programming experience would immediately question the premise of being asked to implement a binary search on a whiteboard because realistically the only way anyone will succeed is by having memorized an implementation.

I don't think this is an especially great question, but I worked at one company that asked this question and most people who got it right did not seem to have an implementation memorized. I say this because they got it right only after writing a buggy version and fixing some bugs.

Another company was in the habit of asking a different question that gets to the heart of the matter of "Can you think with invariants?" but is not nearly as tricky as binary search. That seemed better to me.

It is a very useful question if you do not simply check whether the result is correct, but instead use it as a way to evaluate the candidate's problem-solving skills.

It's Python, so there is no overflow. I considered mentioning this in a footnote but I didn't think it was necessary.

This can still cause signed overflow if left is close enough to INT_MAX and right is close enough to INT_MIN.

The actual overflow-less way to compute the average of two numbers is:

(a/2) + (b/2) + (((a%2) + (b%2))/2)

right is generally not less than left in the context of a binary search.

Reply on news.ycombinator.com