Question 48

The array $A$ of 31 elements consists of a sequence of 0's followed by a sequence of 1's. The first index $i$ where $A[i] = 1$ can be any integer from 1 to 31, or the array may contain no 1's at all (all zeros).

This means there are $31 + 1 = 32$ possible outcomes for the position of the boundary.

Each probe of an array element $A[k]$ returns a binary answer (0 or 1), splitting the remaining search space into two parts. In terms of decision trees, an algorithm with $K$ possible outcomes requires a decision tree with at least $K$ leaves. The worst-case number of probes is the height of the decision tree, which is bounded by:

Standard binary search achieves this theoretical lower bound:

• Probe 1 leaves $\le 16$ candidates.
• Probe 2 leaves $\le 8$ candidates.
• Probe 3 leaves $\le 4$ candidates.
• Probe 4 leaves $\le 2$ candidates.
• Probe 5 identifies the exact index uniquely.
  Hence, the worst-case number of probes is 5.