2 ms·
Yes, it's because you're limited to 2 failures, and yes, "binary search" is a dumb way to describe it since you can't actually do a binary search in that situat
by gjm11 16y ago
Yes, it's because you're limited to 2 failures, and yes, "binary search" is a dumb way to describe it since you can't actually do a binary search in that situation.
Working in increments of 20 floors gives you a worst case of more than 20 drops. 20, 40, 60, 80, 100 (bang), 81, 82, ..., 99 (bang): that's 24 drops.
Your other solution is better, and indeed dropping first at floor 14 is one of the 6 initial choices that minimize the worst-case number of drops. If, subject to minimizing the worst-case number, you also want to optimize the average case (assuming all possibilities are initially equally likely) then doing floor 14 first is optimal.