The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
4.9k 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 ____________.

asked in Algorithms by Veteran (407k points)
edited by | 4.9k 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

+42 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.$
answered 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
+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);
}

answered by Veteran (56.5k 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.

answered by Boss (11.7k 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.
answered 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
answered 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.
answered 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,532 questions
54,126 answers
187,326 comments
71,046 users