3 ms·

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

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-it-nearly.html?m=1 https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

marginalia_nu 5y ago
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.
- anonymoushn 5y ago
  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.
- mannykannot 5y ago
  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.
10000truths 5y ago
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)
- anonymoushn 5y ago
  right is generally not less than left in the context of a binary search.
tylerhou 5y ago
It's Python, so there is no overflow. I considered mentioning this in a footnote but I didn't think it was necessary.

marginalia_nu 5y ago

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.

anonymoushn 5y ago
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.
mannykannot 5y ago
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.

10000truths 5y ago

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)

anonymoushn 5y ago
right is generally not less than left in the context of a binary search.

tylerhou 5y ago

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