CODEWITHSUNDEEP
algorithmbinary-search
Guibao Wang
Guibao Wang

Reputation: 415

Throwing eggs from a building

This is exercise problem 1.4.24 from Robert Sedgewick's Algorithms 4th Edition.

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 is easy to think up, I totally have no idea about the 2lgF solution. Anyway, we are not given the value of F, so where the ground of 2lgF solution is?

Can anyone give some light on this question? Thanks.

Upvotes: 13

Views: 5123

Answers (2)

b.buchhold
b.buchhold

Reputation: 3896

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

2 * logF start at 1, next 2, 4, 8 (i.e., 2^i), once the egg breaks (after log F steps) do binary search in the smaller search space (range < F and hence number of searches < log F) --> exponential search

Upvotes: 18

Timothy Shields
Timothy Shields

Reputation: 79461

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

Another alternative is to carry out the same process until the first egg breaks at 2^(k+1) then start over except adding 2^k to each height: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... You can keep repeating this process to keep reducing the size of the range you do exponential search in.

Upvotes: 5

Related Questions