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)