A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.

The approach would have been easier way for me to answer the question. I wrote something like that to guesstimate the number of git commits on GitHub a project I didn't have time to clone a few years back (I think it was Linux). Basically I started at page 1, then went to 2, 4, 8, 16, etc. When I hit a 404, I went back 50% of the way to the previous number (e.g. if it was page 1024, the previous was 512, then I went to 768). If 50% was a 404, go to back midpoint of lower range (e.g. midpoint of 512 and 768). It if was legit, go to midpoint of upper range (e.g. between 768 and 1024). Wash/rinse/repeat. It was a fun exercise to burn some time on a slow day. If someone actually wants to see the code, reply to this comment and I'll find it, or write it again.

Now I want to go back and study up on that dynamic programming stuff again! Yay inspiration!