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

Best answer
77 votes
77 votes
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{(\text{low + high})}{2}}^{\text{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.$
edited by
25 votes
25 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);
}

edited by
20 votes
20 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.

edited by
9 votes
9 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.
Answer:

Related questions