Binary Search

Binary search is a way of finding a specific node in a tree. It only works on binary trees due to its helpful sorted property. It simply traverses the tree, moving left if the current node is too large or right if it is too small.
Binary search runs in Θ(log⁡(n))\Theta(\log(n))Θ(log(n))
 time for bushy trees, which is also the number of layers in a tree.
The Algorithm
public BST find(BST T, Key sk) {
    if (T == null) {
        return null;
    }
    if (sk.equals(T.key)) {
        return T;
    } else if (sk < T.key) {
        return find(T.left, sk);
    } else {
        return find(T.right, sk);
    }
}
Last modified 3yr ago