7 ms·

Is binary search until the first egg breaks and then increment by 1 for the second egg the best approach?

Someone 14y ago
No. If you first test is at floor N, the two possible consequences are: - egg breaks: you know you the answer is in [1,N], and will have to start stepping by one floor until the second egg breaks - egg does not break: you know the answer is in [N+1, max], and you still have an extra egg to play with. There is an asymmetry here. Because of it, assuming that you can improve upon binary search, N should be less than at half the maximum height. That gives you less information, but decreases the chance that you get into the 'only one egg in hand' endgame.
- tocomment 14y ago
  Hmm I'm not following. What do you do with the first egg if it doesn't break?
  - jgeralnik 14y ago
    You could continue the binary search but that's not relevant anymore - the problem is to minimize the worst case, and your worst case is 51 while there exists a solution whose worst case is 14.
  - lmm 14y ago
    You keep using it. Binary search is the right way of thinking about it, but in some sense you haven't really created an even split by dropping the egg from floor 50 - because you know that you can figure out the correct floor faster using two eggs than one, you could check floors 51-100 much faster than you could check floors 1-50 (Even if you just did the naive binary search approach you first applied - i.e. if the first egg didn't break on floor 50 then drop it from floor 75, and then after that use the second egg to check each floor, it would only take you <=25 goes to find the right floor in 51-100, wheras it would take you up to 50 goes to find the right floor in 1-50). So the correct floor at which to make the first drop is clearly not floor 50. If you dropped the first egg from floor 40 you would do better - it'd take you up to 40 goes to find the right floor if it's below floor 40, and up to 31 or so goes to find the right floor if it's above (because you can reuse the first egg to check whether it's in 40-70 or 70-100). Floor 40 is in some sense a "more binary" place to drop the first egg from than floor 50. If you keep following this line of thought, and remember that whenever you make your approach more efficient, you can recursively apply that more efficient approach to "what do I do if the first egg doesn't break", you'll arrive at the solution given in the article.

No. If you first test is at floor N, the two possible consequences are: - egg breaks: you know you the answer is in [1,N], and will have to start stepping by one floor until the second egg breaks - egg does not break: you know the answer is in [N+1, max], and you still have an extra egg to play with. There is an asymmetry here. Because of it, assuming that you can improve upon binary search, N should be less than at half the maximum height. That gives you less information, but decreases the chance that you get into the 'only one egg in hand' endgame.

tocomment 14y ago
Hmm I'm not following. What do you do with the first egg if it doesn't break?
- jgeralnik 14y ago
  You could continue the binary search but that's not relevant anymore - the problem is to minimize the worst case, and your worst case is 51 while there exists a solution whose worst case is 14.
- lmm 14y ago
  You keep using it. Binary search is the right way of thinking about it, but in some sense you haven't really created an even split by dropping the egg from floor 50 - because you know that you can figure out the correct floor faster using two eggs than one, you could check floors 51-100 much faster than you could check floors 1-50 (Even if you just did the naive binary search approach you first applied - i.e. if the first egg didn't break on floor 50 then drop it from floor 75, and then after that use the second egg to check each floor, it would only take you <=25 goes to find the right floor in 51-100, wheras it would take you up to 50 goes to find the right floor in 1-50). So the correct floor at which to make the first drop is clearly not floor 50. If you dropped the first egg from floor 40 you would do better - it'd take you up to 40 goes to find the right floor if it's below floor 40, and up to 31 or so goes to find the right floor if it's above (because you can reuse the first egg to check whether it's in 40-70 or 70-100). Floor 40 is in some sense a "more binary" place to drop the first egg from than floor 50. If you keep following this line of thought, and remember that whenever you make your approach more efficient, you can recursively apply that more efficient approach to "what do I do if the first egg doesn't break", you'll arrive at the solution given in the article.