Let A be an array of 3k 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] = 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is ____________.

GATE 2017 · Algorithms · Searching · medium

Answer: The worst case number of probes performed by an optimal algorithm is k + 1.

1. Model as ternary search on monotone array: Since the array is monotone (all 0s then all 1s), probing at position n/3 = 3^(k-1) tells us whether the boundary is in the first third or not. If A[3^(k-1)] = 0, boundary is in the last 2/3; probe at 2*3^(k-1) to further narrow to 1/3. Either way, one probe reduces the active range by a factor of 3. This gives recurrence T(3^k) = T(3^(k-1)) + 1.
2. Solve the recurrence: Expanding: T(3^k) = T(3^(k-1)) + 1 = T(3^(k-2)) + 2 = ... = T(3^0) + k = T(1) + k. T(1) = 1 (one probe to confirm the single element). Therefore T(3^k) = k + 1.