Throwing eggs out of a building

Question

This is the task of exercises 1.4.24 from the algorithm of Robert Sedgwick 4th release.

Suppose that you have an N-story building and plenty of eggs. Suppose also that an egg is broken if it is thrown off floor F or higher, and unhurt otherwise. First, devise a strategy to determine the value of F such that the number of broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to ~2lgF. 

While the lgN solution lgN easy to come up with, I am completely 2lgF solution. In any case, we are not assigned the value F , therefore, where is the basis of the solution 2lgF equal to?

Can anyone highlight this issue? Thanks.

Answer 1

logN: start at the top, always cut the search space in half → binary search

2 * logF start with 1, the next 2, 4, 8 (i.e. 2 ^ i), as soon as the egg breaks (after the steps of the log F) performs a binary search in a smaller search space (range <F and therefore the search number <log F) → exponential search

Answer 2

The solution to lg(F) is to do 1, 2, 4, 8, ... until the first egg breaks into 2^(k+1) , and then do a binary search in the range of 2^K to 2^(k+1) .

Another alternative is to perform the same process until the first egg breaks at 2^(k+1) , and then start, with the exception of adding 2^K to each height: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, ... You can continue to repeat this process to reduce the size of the range in which you perform an exponential search.