Keep your data in a tree where every left child is SMALLER and every right child is BIGGER, and searching becomes a game of ‘higher or lower’ — each comparison throws away half of what’s left. Walk it left-to-root-right and it spills out perfectly sorted. Search, insert, delete: O(log n) — when it’s balanced. Slide to search for a key and watch the path narrow.
A binary search tree keeps the invariant: for every node, all keys in its LEFT subtree are smaller and all in its RIGHT subtree are larger. Search descends by comparing (go left if smaller, right if larger), discarding half the remaining tree each step — O(log n) when balanced. An IN-ORDER traversal (left, node, right) visits keys in sorted order. Insertion and deletion preserve the invariant. Unbalanced insertions can degrade it to a O(n) list, which self-balancing trees (AVL, red–black) prevent. A fail-loud self-check throws unless in-order traversal yields sorted keys. ◆ real data structures, node-verified.
A plain BST can degenerate to a linked list (sorted inserts) — O(n); balanced variants restore O(log n). The ordering invariant and sorted in-order traversal are exact.