algorithms – Search in array with blackbox

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.

pseudocode – Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case runningtime of O(nlogn)

Suppose we have an array A(1 :n) of n distinct numbers. For any element A(i), we define the rank of A(i), denoted by rank (A(i)), as the number of elements in A that are strictly smaller than A(i) plus one; so rank (A(i)) is also the correct position of A(i) in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B (1 :m) (for anym >0), returns an element B(i) such that m/3≤rank(B(i))≤2m/3 and has worst-case runtime O(n)1. Example:if B= (1,7,6,2,13,3,5,11,8), then magic-pivot(B) will return one arbitrary number among {3,5,6,7}(since sorted order of B is (1,2,3,5,6,7,8,11,13))