4 ms·

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

• RiderOfGiraffes 17y ago
  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.
  • OmniLarry 17y ago
    For N balls, the other balls can/should be binary searched. It's just a little tricky when it comes to the last two..
    • RiderOfGiraffes 17y ago
      > 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.
      • OmniLarry 17y ago
        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".