Correctness of lower bound proof
The following answer works for a previous variant of the question, in which the goal is to determine which of $x,y,z$ are in $A$. It might be possible to adapt it to the current version, in which the goal is to determine whether or not all of $x,y,z$ are in $A$. One difficulty is that the number of trees of depth $h$ is now $\Theta(2^hh^3)$, so following the same steps would only give a lower bound of $3\log_2 n - \Theta(\log \log n)$.

Suppose that the array $A$ is $1,\ldots,n$. Let $x = i + 1/2$, $y = j + 1/2$, $z = k + 1/2$, where $1 \leq i &lt; j &lt; k &lt; n$ are integers. Let us denote the resulting leaf of the algorithm by $\ell(i,j,k)$.

I claim that if $(i,j,k) \neq (i',j',k')$ then $\ell(i,j,k) \neq \ell(i',j',k')$. Indeed, suppose that $\ell(i,j,k) = \ell(i',j',k')$ although $(i,j,k) \neq (i',j',k')$. Suppose that $i &lt; i'$ (the other cases are similar). Since $i + 1/2 &lt; A_{i+1} &lt; i' + 1/2$, we conclude that in this computation path, the algorithm never compares $x$ to $A_{i+1}$. Suppose that we change $A_{i+1}$ to $A'_{i+1} = i + 1/2$. The new array $A'$ is still sorted, and when running the algorithm on $A',i+1/2,j+1/2,k+1/2$, it still reaches the leaf $\ell(i,j,k)$ (since the only comparison whose answer is different is $A'_{i+1}$ and $x$). We have reached a contradiction, since $x \in A'$, and so we should have reached a different leaf.

Concluding, we have shown that the algorithm tree must have at least $\binom{n-1}{3}$ different leaves (this is the number of possible triples $(i,j,k)$). Since we are only considering runs of the algorithm in which the answers to all comparison queries are either $&lt;$ or $&gt;$, we can ignore all edges labeled $=$, and so we are left with a binary tree, whose depth must therefore be at least $\log_2 \binom{n-1}{3}$. This is a lower bound on the number of comparisons in the worst case.

When $n \geq 4$, we have
$$
\binom{n-1}{3} = \frac{(n-1)(n-2)(n-3)}{6} \geq \frac{(n-3)^6}{6} \geq \frac{(n/4)^3}{6} = \frac{n^3}{384},
$$
since $n-3 \geq n/4$. Therefore for $n \geq 4$ the number of comparisons must be at least
$$
\log_2 \frac{n^3}{384} = 3\log_2 n - \log_2 384.
$$
When $1 \leq n \leq 3$, we must still make (say) at least one comparison, and this allows us to obtain a lower bound of $3\log_2 n - c$ valid for all $n \geq 1$ (details left to the reader).