Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a…

Concept: In a monotonic boolean array of size n (all 0s followed by all 1s), locating the boundary index — the smallest i with A[i] = 1 — is a search among n + 1 possible outcomes (the boundary can fall at any of the n positions, or nowhere if the array is all 0s). Binary search on a monotonic array is optimal for this: each probe halves the remaining candidates, so the minimum worst-case number of probes is ceil(log2(n + 1)).

Application:

1. Here n = 31, so there are n + 1 = 32 possible boundary positions (index 0 through 31, where 31 means the array is all 0s).

2. Apply the formula: number of probes = ceil(log2(n + 1)) = ceil(log232).

3. Since 25 = 32 exactly, log232 = 5 with no fractional remainder.

4. So ceil(log232) = 5 — the ceiling changes nothing here because 32 is an exact power of two.

Cross-check: 24 = 16 and 25 = 32, so 5 is indeed the smallest exponent k with 2k ≥ 32, confirming that 5 yes/no probes are both necessary and sufficient to distinguish all 32 outcomes. This matches the standard binary-search recurrence T(n) = T(n/2) + O(1), which resolves in ceil(log2(n + 1)) levels.

Result: The worst-case number of probes performed by an optimal algorithm is 5.