Register

NIELIT 2017 DEC Scientist B - Section B: 8

• retagged by
1,130 views
1 votes
1 votes

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

  1. $2$
  2. $4$
  3. $3$
  4. $5$
• retagged by
User Avatar

3 Answers

2 votes
2 votes
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.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
6 answers
2
admin asked Mar 30, 2020
2,452 views
NIELIT 2017 DEC Scientist B - Section B: 2
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
According to the given language, which among the following expressions does it correspond to ?Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.$(0+1+0+1+0...
User Avatar
0 votes
0 votes
2 answers
3
admin asked Mar 30, 2020
2,343 views
NIELIT 2017 DEC Scientist B - Section B: 3
Using bisection method, one root of $x^4-x-1$ lies between $1$ and $2$. After second iteration the root may lie in interval: $(1.25,1.5)$ $(1,1.25)$ $(1,1.5)$ None of the options.
Using bisection method, one root of $x^4-x-1$ lies between $1$ and $2$. After second iteration the root may lie in interval:$(1.25,1.5)$$(1,1.25)$$(1,1.5)$None of the opt...
User Avatar
0 votes
0 votes
4 answers
4
admin asked Mar 30, 2020
1,620 views
NIELIT 2017 DEC Scientist B - Section B: 4
In a cache memory if total number of sets are ‘$s$’, then the set offset is: $2^8$ $\log_2s$ $s^2$ $s$
In a cache memory if total number of sets are ‘$s$’, then the set offset is:$2^8$$\log_2s$$s^2$$s$
User Avatar
Link Copied!