How may occupied positions are there?

Question

Consider an array, that can have a huge ( or infinite ) number of positions, but only the first $n$ positions are occupied(only $n$ of them contain valid elements), and the remaining are empty. Consider that, for us, $n$ is unknown.

A program has been constructed that can answer questions about the number of occupied positions of the array. The program gives only answers of the form YES or NO. So, the questions that we ask should have a suitable form, so that an answer of the form YES or NO makes sense( for example: has the array more than 100 occupied positions?).

Describe what kind of questions you would ask the program and in which order, so that you determine the exact number of occupied positions of the array, i.e to find $n$. It is not allowed to ask more than $O(\log n)$ questions.

How can we ask $O(\log n)$ suitable questions to find an upper bound and how can we find, then, the exact number of occupied positions of the array?

EDIT: That's what I have tried:

 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)?

Answer 1

You're basically looking for a series of questions that resemble a binary search. Binary search runs average O($\log n$) and worst O($\log n$).

Questions like, "is position n occupied", should suffice. Make sure each subsequent question tries to cut the problem size in half.

Note: Try asking for an extremely large value, if yes, double the value size, if no, reduce the value size by half and ask again.

Answer 2

First ask "Is 1 occupied?", then, "Is 2 occupied?", "Is 4 occupied?", "Is 8 occupied?", and so on, until you get the answer, "no". This will take $\log_2n$ questions (give or take a fraction).

You now know $k$ such that $n$ is between $2^k$ and $2^{k+1}$, and binary search inside that interval will get you the answer in another $\log_2n$ questions.