Binary Search

Requirements

• Must maintain BST property: left subtree keys ≤ node key ≤ right subtree keys

• Internal nodes store keys or key-value pairs

• External nodes (leaves) are empty/don't store items

Elements

• Must be a total order relationship

• Must be comparable

Ideal/Worst Tree Structures

Ideal: Balanced tree with height O(log n)

Worst: Linear/degenerate tree with height O(n) (resembles linked list)

Time Complecity of Binary Search

Balanced - O(logn)

Unbalanced - O(n)

In arrays in all cases - O(logn)

Space Complexity

O(n)

• For both BST and arrays

Binary Search (Array) Requirements

• Sorted array

Binary Search - Remove

No kids: Just cut

One kid: Promote

Two kids: Inorder swap

Binary Tree - Insert

Search, Reach Leaf, Plant New Node

Binary Search - Search

Compare, Left-Right, Repeat

Binary Search Methods - Time Complexity

Worst Case: O(n)

Best Case: O(logn)

(O(1) - for removal if one node)