Halve the work at every step
In a binary search tree every node has at most two children, with smaller values on the left and larger on the right. Searching discards half the remaining tree at each step — O(log n) when the tree is balanced. Databases use close relatives (B-trees) for every index.
Insert, search, in-order
class BST {
root = null;
insert(value) {
const node = { value, left: null, right: null };
if (!this.root) { this.root = node; return; }
let cur = this.root;
for (;;) {
const side = value < cur.value ? "left" : "right";
if (!cur[side]) { cur[side] = node; return; }
cur = cur[side];
}
}
has(value) {
let cur = this.root, steps = 0;
while (cur) {
steps++;
if (value === cur.value) return { found: true, steps };
cur = value < cur.value ? cur.left : cur.right;
}
return { found: false, steps };
}
inOrder(node = this.root, out = []) {
if (!node) return out;
this.inOrder(node.left, out);
out.push(node.value);
this.inOrder(node.right, out);
return out;
}
}
const prices = new BST();
for (const p of [180, 90, 260, 50, 120, 220, 300]) prices.insert(p);
console.log(prices.inOrder());
console.log(prices.has(220), prices.has(100));Insert already-sorted data and the BST degenerates into a linked list (O(n)). Self-balancing trees (AVL, red-black) fix that automatically.