GATE CSE 2017 Set 1 | Question: 48

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\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.

Comments

code - https://onlinegdb.com/SkxsC0CFH

---

@Ritwik Mishra 1

wouldn’t the 3^rd probe suffice for finding?

---

Suppose I wanted to add another condition to the problem i.e. the array must contain atleast 3 0's.Will the no.of probes be "6"??

Answer 1

All 0's are followed by 1's . So elements are sorted, we can apply Binary Search i.e log2n.

Here he is asking for minimum so take a ciel.

Ciel(log2(31))=5.00.

Answer 2

Ans:  6

a[0..3] = 0

a[4..31] = 1

Binary search is as follows (indexes of array a is given below):
i - j ... middle
0-31...15

0-15...7

0-7...3

3-7...5

3-5...4

3-4...3

After this i > j

Comments

@sameer2009 ,

Your naive binary search has only one condition to terminate the search which is i > j

If we do some modifications in the code keeping condition i > j then we can achieve under $5$ probes only.

You may argue that modification is not permitted. On this argument, I would like to say that, this binary search is the best algorithm to this question task. We agree. But on the implementation basis, there exists better program to do a binary search in this particular case. I think we should approach worst case using best algorithm supported by optimal program but not with rudimentary code.

Answer 3

If you go through the book - Skiena- the algorithm design manual, it has clearly stated that we can find a transition point in sorted array using Binary search in ceiling(logn) comparisons.

The concept is if have a sorted array with sequnce of zeros followed by sequence of 1 then we can find the smallest index 'i' such that array[ i ] is '1', which is called the transition point.

If you analyze the question, we have same thing asked in the question i.e. the transition point.

We have n=31, hence we require maximum of ceiling (logn) probes i.e. ceiling(log 31)= 5 probes.

P.S.: This question was asked on a direct concept.

Answer 4

Here Optimal algorithm would be Binary search with little modification. The question implies it is a sorted array of 0's followed by 1's. So 0111...1 or 00...01 or any combination of {$0^{+}.1^{+}$} of size 31.

We are taking 2 index variable i & j and it will run until i<j.

Binary Search (Modified):-

int i, j, k;
i= 0; j = 30;
do {
k = (i+ j) / 2;
if( A[k] ==  0)

i = k+1;

else j = k-1;
} while (i < j) ;

 

If(A[j] == 0)  printf(" J+1 is the smallest index for value 1 ");

else   printf(" J is the smallest index for 1 ") ; 

 

In the below example we are taking an array of 7 element to understand the function of this algorithm, rest is same.

 

Here 2 probes are necessary to reach first 1's or last 0's in this sequence, and again 1 probe to check what value is in A[j] to find the correct index for first 1's.

So in general total no. of probes needed for this sequence of length 31= $\left \lceil Log 31 \right \rceil$ = 5

Comments

so as per your example , ceil(log7 base 2) = 3 , but no of probes req is 3 , why such ambiguity ?