I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.
Given a sorted array $A$ (of $n$ distinct elements) and three elements $x$, $y$, and $z$, where $x < y < z$. The problem is to determine whether $x$, $y$, and $z$ are in $A$ or not. Prove that any comparison-based algorithm for this problem needs at least $3\log n-c$ comparisons in the worst case, where $c > 0$ is some constant.
My current proof using a decision tree goes as follows: A comparison based algorithm must have at least 2 outcomes per a single comparison. For example: >= or <. It can also have 3 outcomes: < or = or >. But it has to have at least two.
When trying to decide whether an element is in the array or not it could be equal to any of the $n$ elements or it might not be in the array. Thus we have $n+1$ leaves in the decision tree.
Because of this the height of the decision tree is at least $\log_2(n+1)$. This is a lower bound for deciding whether one element is in the array or not. If we want to decide if the 3 elements $x, y, z$ are in the array or not and we know that $x< y< z$ we can use this information to speed up the search by searching for $y$ first.
For example if the outcome of the first comparison is < then since we know that $x < y$ we can skip that comparison when searching for $x$ and save at least a step. Similarly, if the outcome of the first comparison is > then since we know $y < z$ we don’t have to redo that comparison when searching for $z$ and save at least one step.
So if the search for $y$ starts with some constant $c$ left-branches we save that many steps when searching for $x$ and if the search for $y$ starts with $c$ right-branches we save that many steps when searching for $z$.
Thus, if it takes $k$ steps in the worst case to search for the 3 elements a lower bound is: $$ k \ge 3\log_2(n+1)-c \ge 3\log_2 n-c, $$ where $c$ is some positive constant.
Is this a correct proof? What I am unsure about is if the last statement is ok, where I just discard the "+1". And whether this holds true for "any comparison based algorithm". Any critique or suggestions are greatly appreciated.