Given array $A(1..n)$, and black box, and a number $x$. we want to

find out a $i$ such that $A(i)=x$. Our black box have three inputs,

array $A$ and at most $k$ numbers from set $S={1,2,…,n}$, and $x$.

Black box return true if there is $iin k$ that $A(i)=x$. How we can

show that the number of times we use black box is $O(frac{n}{k}+log

k)$?

I think as follow: divide set $S$ to $k$ sets with size $frac{n}{k}$ and then we use block at most $k$ times. Now if after $k^{th}$ the black box return true the on array $A$ we search an interval with size $k$. So the number of calls are $O(frac{n}{k}+k)$. But the term $k$ contradict with $log k$. Any help be appreciated.