GATE CS 2017 Set 1 Q48 — Searching, Sorting, Hashing

The problem asks for the minimum number of probes in the worst case to find the first transition from $0$ to $1$ in a sorted array $A$ of size $31$. This can be modeled as a binary search problem.

Method 1: Decision Tree / Information Theory

Let the array indices be $0, 1, \dots, 30$. The first occurrence of $1$ can be at any of these $31$ indices, or there might be no $1$ at all in the array. This gives us a total of $32$ possible outcomes.

Each probe at an index $A[j]$ yields a binary outcome: either $0$ or $1$. Therefore, any decision tree representing an optimal search algorithm must have at least $32$ leaves.

The minimum height (worst-case number of probes) of a binary decision tree with $L$ leaves is given by:

Method 2: Binary Search Execution

We can find the transition index using standard binary search over the range $[0, 30]$:

1. Probe 1: Query the middle element at index $15$.
   • If $A[15] = 1$, the first $1$ lies in the range $[0, 15]$ (size $16$).
   • If $A[15] = 0$, the first $1$ lies in the range $[16, 30]$ (size $15$).
   In the worst case, the remaining search space is of size $16$.
2. Probe 2: Halves the search space to size $8$.
3. Probe 3: Halves the search space to size $4$.
4. Probe 4: Halves the search space to size $2$.
5. Probe 5: Halves the search space to size $1$, uniquely identifying the transition index.

Thus, the worst-case number of probes performed by an optimal algorithm is 5.