Mapping a uniform draw to a discrete law

You have a generator of uniform $U(0,1)$ numbers and a discrete distribution taking values $x_1,\dots,x_n$ with probabilities $p_1,\dots,p_n$. How do you produce samples from that distribution?

Inverse transform on the cumulative probabilities. Precompute $c_k=p_1+\dots+p_k$, draw $u$, and return the first $x_k$ with $u\le c_k$. A linear scan costs $O(n)$ per draw; binary search on the cumulative array gives $O(\log n)$, and Walker's alias method gives $O(1)$ per draw after $O(n)$ setup.