# Binary tree for 2 elements

I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?

If I want to search for an element 2, it will make 2 comparisons. If I want to search for an element 22, it will also make 2 comparisons. But according to formula Θ(lg n), with n=2, it should make only one comparison in worst case. I'm not able to connect these 2 facts. Please help me. (For any even number of elements, I'm not able to draw tree. Because at some point, left side has one node and right side has 2 nodes)

• The formula $\Theta(\log n)$ defines a class of functions. It has no particular value at any given point. – Yuval Filmus Jan 7 at 18:09
• So you mean to say Θ(lg n) is just a classification. The exact number of comparisons will not necessarily match with values of Θ(lg n). – gmail user Jan 7 at 19:41
• Not exactly. My point is that $\Theta(\log n)$ doesn’t specify any particular value at any single $n$. It only stands in for a function growing logarithmically. The function could be $\log n$, or $2\log n$, or $\log n + \log \log n$ - the notation $\Theta(\log n)$ doesn’t specify which. – Yuval Filmus Jan 7 at 20:19
• Thanks for reply. Diagram of even numbers has really baffled me. Would you please give one example diagram for lets say n=8? – gmail user Jan 7 at 20:33
• Perhaps the Wikipedia entry on binary search trees contains such diagrams. – Yuval Filmus Jan 7 at 20:37