How binary search has O(log(n)) complexity??

Answer 1

In computer science we usually take log (base 2) as default.

If n=8 then (log(base 2) n) would be 3, which is the height.
The 8 will split into 4 then 4 into 2 then 2 into 1.
See 3 times, so the height is 3.

Answer 2

Binary tree is an interesting data structure with many implementations. Look at this lesson to get a quick idea

https://www.sololearn.com/learn/322/?ref=app

Binary tree is another common implementation of the binary tree, which is described here

""
As the keys are stored in a particular order, the principle of binary search can be used for lookup.
We start from the root and compare the key. if the root has the key, it is returned as the result.
If the key is greater than the root, the right subtree is recursively checked.
If the key is less than the root, the left subtree is recursively checked.
The recursion continues until the key is found.
""

And thus it ensures the lookup to be O(log n) - Try to understand with the diagram

https://www.sololearn.com/learn/686/?ref=app

I think those 2 resources are enough to get an idea but feel free to ask any question :)

Answer 3

Thanks