Let $A$ be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index $i$ such that $A[i]$ is 1 by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ________.

The array $A$ of size $n = 31$ is sorted in non-decreasing order ($0$s followed by $1$s).

The number of zeros in the array can range from $0$ to $31$. Therefore, there are $31 + 1 = 32$ possible configurations for the index of the first occurrence of $1$ (including the case where there is no $1$).

Each probe (comparison) at an index tests whether the value is $0$ or $1$, which gives a binary outcome and partitions the remaining search space into two parts.

By information theory, any comparison-based algorithm represented by a binary decision tree with $K$ possible outcomes requires at least $\lceil \log_2 K \rceil$ probes in the worst case:

An optimal binary search algorithm can always find the transition point in at most $5$ probes.

Thus, the worst-case number of probes is 5 [cite: 2].