CS61B Guide
Search…
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))
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);
}
}
Copy link