Question

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 _____.

Answer 1

Worst case of the given problem is when a single 0 is followed by all 1’s i.e.

0111111111111……

Also, worst case can also be considered as when all 0’s are followed by single 1.

000000000………………1

Since, in both the cases there is a sorted sequence of 0 and 1 and for sorted sequence binary search is preferred.

At each stage, \(\frac{{low + high}}{2}\) element index is compared and if it is 1, search towards left and if it is 0 search towards right.

Total worst-case number of probes performed by an optimal algorithm is = \(lo{g_2}31\) = 5