Hacker News Reader

Comment by xhuang | Hacker News Reader

just wondering for this question("how strong is an egg"), i think binary search will be the minimum tries, so its quite useful.

View on HN

That turns out not to be the case. Binary search doesn't help, binary doubling doesn't help, even though these are often thought to be the best. Indeed, the solution given on this site used binary doubling and claimed it to be optimal. It was wrong. It was posted here some time ago.

The solution, once found, is simple to prove optimal, but most people don't seem to know how to do that.

Most people don't find it.

For N balls, the other balls can/should be binary searched. It's just a little tricky when it comes to the last two..

  > For N balls, the other balls can/should be binary searched.

Interesting assertion. Can you prove that? Can you give a provably minimal search pattern?

  > It's just a little tricky when it comes to the last two.

Another interesting assertion. It seems to me that the case of exactly two balls is trivial, once the solution is found.

Sorry, can't find the link, but it was a Topcoder problem at least 5 years ago.

Well, it is trivial with two balls, once you get it, but it's tricky with respect to "just binary search".

Reply on news.ycombinator.com