A real problem from the hospital.
Suppose we have $n$ blood samples to test HIV. We don't want test them one by one, since the cost is huge and most people don't have a positive result. So we try to merge them into groups, and then we just use the machine to test groups. Assume we have $k$ positive in $n$ samples, but we don't know $k$. Does a algorithm of $O(k\log_2n)$ tests (times of using the machine) exist?
Hint: if $k=1$ a binary tree (split the samples in half, mix each half, test) works. If $k \ll n$, suppose you do a binary tree and quit testing any batch that shows negative?