Ball Break Point Problem

Question

I came across following question:

There is a building with N floors. We have a balls of same property and have a breaking point of X floor. i.e, If ball dropped from X+1 floor then the ball will break. if ball is dropped from X or less than X then it wont break. Now design an algorithm to find X if N is given.

My Solution:

Drop the ball from N/2 floor. If ball breaks then X < N/2. Else X > N/2. Repeat this process till X is found. but If X is N/2+1 or N/2-1 the number of steps to find X are high.

Is there a better way to Find X?

Answer 1

This is the best way to Find $X$. Your algorithm is basically binary search, which is optimal in terms of comparisons.

Let $T(N)$ be the number of ball-drops required in a building with $N$ floors to find $X$. \begin{align} T(1) = & 0 & \text{(no balldrop with one floor)}\\ T(N) = & T(\frac{N}{2}) + 1& \text{(drop ball once, repeat on upper/lower half)} \\ = & T(0) + 1 + \ldots + 1 \in \mathcal{O}(\log n) \end{align}

Each floor $i$ of the $N$ floors can be represented as binary number with $\lceil \log_2N\rceil$ bits. To identify one number out of a set of $N$ numbers, you have to look at each single bit, hence this takes you $\lceil\log_2 N\rceil \in \mathcal{O}(\log n)$ comparsons. So in terms of complexity, there is no better way to find $X$.

Of course, you could check one floor above as well as one floor under the current floor, which covers the cases $X=\frac{N}{2}+1$ and $X=\frac{N}{2}-1$, respectively. But you this does not improve your algorithm in terms of $\mathcal{O}$ complexity. Furthermore, you can always construct another worst case for you algorithm, since $N$ is unbounded: The improved algorithm performs poorly when $X=\frac{N}{2}-2$ or $X=\frac{N}{2}+2$. So you could add those cases as well. But then $X=\frac{N}{2}-3$ and $X=\frac{N}{2}+3$ becomes a problem ...