edited by
21,452 views
56 votes
56 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\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 ____________.

edited by

10 Answers

4 votes
4 votes
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.
3 votes
3 votes
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
1 votes
1 votes

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.

0 votes
0 votes

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

Answer:

Related questions