A sorted linked list with express lanes: coin flips decide how tall each node is, and a search runs right on a high lane, then drops down.
This interactive visualization needs JavaScript.