NIELIT 2017 DEC Scientist B - Section B: 8

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

• A. $2$
• B. $4$
• C. $3$
• D. $5$

Comments

same as https://gateoverflow.in/118331/gate2017-1-48

Answer 1

If we apply binary search to find first occurrence of 1 in the list, it will give smallest index i.

In this array, sequence of 0's is followed by sequence of 1's so it is sorted. So we can apply binary search directly.

Number of probes performed = ceil(log31 base2) = 5

So, correct answer is D.

Answer 2

Option D is correct

Answer 3

OPTION

D

 

SIMPLY APPLY BINARY SEARCH