0
$\begingroup$

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

enter image description here

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.

$\endgroup$

closed as off-topic by GoHokies, Anton Menshov, Bill Greene, Mauro Vanzetto, Christian Clason Jan 5 at 13:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "General computer science questions are off-topic here, but can be asked on Computer Science Stack Exchange." – GoHokies, Anton Menshov, Bill Greene, Mauro Vanzetto, Christian Clason
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Ok, I'll ask this question on Comp Sci SO $\endgroup$ – gmail user Jan 7 at 14:32
1
$\begingroup$

In your example, the binary tree is correct in that the right node is greater than the parent node, but it is not optimal because the search tree will not be balanced. The fact that the root node is 1 will mean that for the first comparison, the search algorithm will navigate right.

What is happening is the binary search tree in your example is acting as a linked list with a time complexity of Θ(n) instead.

This can been seen in the "Searching" here: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.