Binary search

The binary search is used to find a value by splitting the interval into two at each iteration. For that, the list/array should be sorted.

We can find the final result if it's a discret interval, like an index in a sorted list. However, if it's a continuous, we need to give a stopping condition (precision).

Binary search tree

A binary search tree is like a binary tree, but one child node is larger while the other is smaller than the parent node.

When nodes are inserted or deleted from the tree, it has to re-balance itself to keep this left→larger, right→smaller logic.

Time complexity	Mean case	Worst case
Search	$\mathrm{\Theta }(\log n)$	$O(n)$
Insert	$\mathrm{\Theta }(\log n)$	$O(n)$
Delete	$\mathrm{\Theta }(\log n)$	$O(n)$

Complexity

Time complexity

• Worst case: $O(\log n)$
• Best case: $\mathrm{\Omega }(1)$
• Mean case: $\mathrm{\Theta }(\log n)$

Space complexity

• Worst case: $O(1)$