Finding all unique elements from a big sorted array in log n time?

Question

I have a very big sorted array. How can I count or print all the unique elements of an array??

Suppose my array is [2,3,3,3,4,6,6,7] then output should be 2,3,4,6,7

I know to do it in a n(complexity) time. But interviewer asked me to do this in log n time?? Is it possible?

Answer 1

Here is an algorithm which requires O(logn*k) where k is unique elements:-

set uniQ
int ind = 0;

do {

 uniQ.add(arr[i]);
 ind = BinSearchGreater(arr,arr[ind],ind+1);
 if(ind >= arr.length)
   break;

} while(true);


BinSearchGreater(arr,key,start_ind) : returns index of first element greater than key in subarray starting at start_ind 

Time complexity :- Note this algorithm is only good when no of unique elements are small. This is asymptotically O(n*logn) if all are unique so worse than linear.