Find the number of occupied positions

Vote count:

0

Consider an array that can have a huge (or even infinite ) number of positions, but only the first n positions are occupied, i.e. only n of them contain valid elements and the others are empty.

A program has been constructed to help the students of a CS Department to think more algorithmically. The program can answer questions for the number of occupied positions of the array. The program gives ony answers of the form "YES" or "N0". So the questions that are done to the program should be of a specific form so that an answer of the fom "YES" or "NO" makes sense. We cannot ask more than O(log n) questions.

HINT: We have to ask first O(log n) suitable questions to find an upper bound for the number of occupied postions of the array and in addition we have to ask O(log n) questions to find the exact number of them.

I tried to write this algorithm:

Positions()
{
  int pos=1, low=2, high;
  char answer;
  printf("Is the number of occupied positions equal to 1? \n");
  scanf("%c",&answer);
  if (answer=='YES'){
     printf("1 position is occupied.\n");
     return;
  }
  answer='NO';
  while (answer=='NO'){
         pos=2*i;
         printf("Is the number of occupied positions  <= %d ? \n",pos);
         scanf("%c",&answer);
    }
    high=pos;
    return BinarySearch(low, high);
}

And the BinarySearch that we use is the following:

BinarySeach(low,high){
   int mid=low+floor((high-low)/2);
   char answer;
   printf("Is the number of occupied positions equal to %d", mid);
   if (answer=='YES') return mid;
   else{
        printf("Is the number of occupied positions <= %d", mid);
        if (answer=='YES')  BinarySeach(low,mid-1);
        else BinarySeach(mid+1,high);
   }
}

Is it right? If so, how could it be justified that the time complexity of the algorithm Positions() is equal to O(logn)?

asked 36 secs ago

evinda

226

Find the number of occupied positions