it can be done in O(logk)
i am writing small pseudo code with function 'algo'
algo(array,k)
{
if(array[k/2] isduplicate) return k/2; /*isduplicate can be checked in O(1) */
else if(array[k/2]==k/2 && notduplicate) return algo(right_half array,k/2);
else if(array[k/2]!=k/2 && notduplicate) return algo(left_half array,k/2);
}
u can see at each iteration we are throwing away half array, so
T(k) = T(k/2) + O(1)
T(k) = O(logk)