6 ms·
For N balls, the other balls can/should be binary searched. It's just a little tricky when it comes to the last two..
by 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 agoSorry, 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".