Let \(A\) be an array of 31 numbers consisting of a sequence of 0's followed…
2017
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 ____________.
Attempted by 74 students.
Show answer & explanation
Correct answer: 5
Answer: 5 probes.
Explanation: The array has 31 entries and consists of some number of 0's followed by 1's. The transition from 0 to 1 can occur in any of 32 possible positions (before the first element, between any two elements, or after the last element).
Information-theoretic lower bound:
To distinguish among 32 possibilities requires at least log2(32) = 5 binary questions (probes). So any algorithm needs at least 5 probes in the worst case.
Matching algorithm (achieves the bound):
Use binary search on the index range. Probe the middle index of the current interval; if it is 0, continue to the right subinterval; if it is 1, continue to the left subinterval (including that position as a candidate).
Each probe halves the number of possible transition positions. Starting with 32 possibilities, after 5 probes there is exactly one possibility left.
Therefore the worst-case number of probes performed by an optimal algorithm is 5.
A video solution is available for this question — log in and enroll to watch it.