The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
5.1k views

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

in Algorithms by Veteran (418k points)
edited by | 5.1k views
0
It can be done with 4  comparison .
It is clearly mention that 0's sequence is followed by 1's sequence. Mean there atleast one 0 and followed by 1's sequence.   or  there is many zeros and atlest one 1 at the end.

In worst case i can search min index of 1 in 4 step because ,last camparision is not required. Because list will cotain 2 element .
That is 0 followed by 1. Because it is necessary candition there should be atlest one 0 or there should be atlest one 1 .
+8

@vikram No you need to do the last probe also, consider this

Array
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
      3   4   2               1                              

first row is index, second row is data and third row is for probing

5th probe is necessary to get the right answer i.e. index E

0
what does probe and optimal actually mean?
+1
0

Why you have taken a[16] , we have to take 

 m := floor((L + R) / 2) i.e. floor((0+30)/2)

correct me if i m wrong.

0
Why it can't be this sequence 0000000.....01. It takes 6 probes???

6 Answers

+43 votes
Best answer
Here, since $0$s are followed by $1$s so we have a sorted sequence and we can apply binary search.

At each stage we compare with ${\frac{(low + high)}{2}}^{th}$ element index and if it is $1$ we check left and if it is $0$ we check right.

Total worst case no. of probes is $\lceil \log_{2}{31}\rceil=5.$

So, answer is $5.$
by Active (3.4k points)
edited by
+2
how 5 comparisions are enough to do this?
01111111111....
how can we recognize the smallet index with 5 comparisions in above example?
+2
16-8-4-2-1 binary searching
+1
Is no. of probes same as no. of comparisons made in this case of Binary Search?? I want to ask what is the meaning of 'probes'?
–1

Actually not, only 4 probes are sufficient here because once you find a 1 at 2nd position, you're certain that i=2. So, this 01111.. comes under the average case.

Whereas, the sequence 001111.. or 000111.. comes under the worst case and requires the probes 16,8,4,2,3. The probe at 3 is required after finding 0 at 2nd position to ascertain whether i=3 or 4.

And by probe the question means the number of locations that the program dereferences.

0

 Vidhi Sethi   No not same.

+1
Is no.of probes is the no. of times we perform binary search i.e. one binary search == one probe
+12
Yes one iteration of binary search = one probe
0
I think answer should be 1 probe.                                                                                                     You can add the entire elements in the array ------------------say we got value 'x'

             then  arr[31-x] will directly give us the first slot with value '1'
0
it is asking for worst case
0

I think it should be 6 in case if the 1 is present at 31st position. 

indexes are staring from 0.

15,22,26,28,29,.....30

Now (29+30)/2 is always 29.

So we have to check the last value either at the first time or the last time forcefully. divide and conquer will not let us check the last index.

Also if the 1 is not present then also same scenario. 

 

Please justify.

 

+1

@abhishek_tyagi Here you are not incrementing the value of i by 1. As initially i and j will be 0 and 31 respectively then k=(0+31)/2 = 15, now the index of  will be incremented to i+1 so i becomes 16. Now again calculate the new value of k, if arr[k]== 0 then go to the right or move to left.

If we consider the sequence 0000...01 as the worst-case then we would be looking at  this sequence :- 16,24,28,29,30 => 5 .

0
Why are we not considering the case when we probe the intended element at 31st index? Shouldn't the probe sequence be 15 23 27 29 30 31 and hence 6 probs instead of 5? Though I know log 31 will give 5 as answer but when I am doing it with pen and paper I am getting 6. Please correct me if I am wrong.
+19 votes

 

it should not take more than 5 probes 

#include <bits/stdc++.h>
using namespace std;
#define N 100
void display(bool a[]) {
  int i=0;
  while(i<31) printf("%2d ",a[i++]);
}
void assign(bool a[],int zeros) {
  for(int i=0;i<31;i++)
    (i<zeros)?a[i] = 0:a[i] = 1;
}
int main() {
  srand(time(NULL));
  bool a[31];
  // header
  for(int i=0;i<31;i++) printf("%2d ",i);
  printf("\n\n");
  int max_probes = 0;
  for(int iteration = 1;iteration <= N;iteration++) {
    int zeros = rand()%32;
    assign(a,zeros);
    sort(a,a+31);
    int low,high,mid,ans;
    std::vector<int> seq;
    
    low = 0;
    high = 31;
    while(low < high) {
      mid = low + floor((high - low) / 2);
      seq.push_back(mid);
      if(a[mid] == 0) {
      low = mid + 1;
      ans = low;
        if(a[mid + 1] == 1) break; 
      } else {
      high = mid;
      ans = high;
      if(mid > 0)
        if(a[mid - 1] == 0) break;

      }
    }

    display(a);
    printf(" | probes=%d  ",seq.size());
    for(auto e:seq) printf("%d ",e);
    printf(" | at = %dth\n",ans);
    //if(ans == 15) printf("\nHHH=-------------\n");
    max_probes = max(max_probes,(int)(seq.size()));
    seq.clear();	
  }
  printf("%d\n",max_probes);
}

by Veteran (56.7k points)
edited by
+1
the meaning of probe ? is it ok ?
0
Can u explain diagram a bit?

According to the question there are 31 numbers,

where atleast one 0 followed by thirty 1's

So, 01111111..... in worst case

And by binary search there will be maximum 5 comparisons
+2
the purpose of the diagram is to emphasize that one iteration of while loop counts one probe only. What happens inside one while iteration (finite no of comparisons ) does not change the probe count.
0

I cannot understand ur program

Can u explain a bit?

https://ideone.com/4ZG8jN

+1
It randomly assigns some no of zeros and ones in an array of $31$ elements in the given order. Then binary search on the array to find the first occurrence of $1$. I put this whole thing inside a iteration loop to see results for different array configuration ( different nos of $0/1$'s) and this difference is made possible by random utility which determines the no of zeros to fill) and Total no of iteration is $100$
0
but is 100 iteration can take all combinations?

As u r taking random order, So, one 0 and thirty 1's can can take 31 numbers rt?
+1
It may not, but $100$ is pretty large number compared to $31$ length
0
the above problem is nothing but finding the first occurence of a number in a sorted array which can be done in O(logn) time thats it it gives u 4.something and they asked the minimum number of probes so take ciel
0

DOES PROBE MEAN NO. OF TIMES WE DIVIDE ARRAY A USING BINARY SEARCH????

0
To 'probe' means to check/test (here, it means to check if the number at that location is 0 or 1)
+9 votes

Ans is ceil(log 31) =5   Why ceil??

Take another example.
1 2 3 4 5 6 7   (7 elements... We are searching for 1)
Iteration 1:  1 2 3 4  (4!=1)     5 6 7 cancelled out.
Iteration 2:  1 2  (2!=1)          3 4 cancelled out.
Iteration 3:  1  (1==1)

3 = ceil (log 7) you know...   hence.
Here ans is  ceil (log 31) = 5        (base is 2 every where)

Here in this question, the number are sequence of zeros followed by sequence of ones.
We have to find the first index from where 1 starts. Right ?
So if you got a '1' just check if it's previous element is 0. Thats it. If it is not 0, continue binary search.
Worst Case happens when all are 1 or only first element is zero & rest are one.
111111...11  or
01111.....11  or
0011.......11  or
00011.....11  or
.
.
.

ceil(log 31) = ceil(log 30)  =  ceil(log 29) =............
only log 16 will give 4 ,   anything greator than 16 elements with ceil will give 5 as answer.

Worst case will also happen for
00.......00
00.......01
.
.
.
You got 0, here you will move right side to find the first index from where 1 starts.

by Boss (12k points)
edited by
0
Great explanation bro :-)
+6 votes
Do Binary search.
Worst case 000000000000..01 (i.e. n-1 0s and last one is 1).
It will take log n time worst case. Hence log 31 = 5.
by Active (2k points)
0
can u beleive it i made a blunder, i made it 4.95 (log 31).. should have made it 5
0
Actually, I do relate to that.
+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
by Active (2k points)
+2

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

+3 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.
by (399 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,896 questions
55,153 answers
190,576 comments
85,317 users