Finite categorical sampling by inverse CDF and binary search

Input a nonempty finite list of outcomes $1,\dots ,r$ ($r\ge 1$) with probabilities $p_i\ge 0$ and ${\sum }_{i=1}^r{p}_i=1$, and either an ideal bit-stream uniform $U\in [0,1]$ as in Disjoint streams of independent fair bits produce independent uniform variables or a $b$-bit midpoint $U_b\in (0,1)$ as in Midpoint bit discretization has bounded coupling and CDF error. Write $v$ for the supplied input. Let $C_0=0$ and $C_i={\sum }_{j=1}^i{p}_j$.

1. If $v=0$, return outcome $1$. This assigns the ideal uniform's null zero-endpoint event an explicit value.
2. Otherwise initialize integer bounds $L=1$, $H=r$. While $L<H$, set $j=\lfloor (L+H)\mathrm{/}2\rfloor$. If $v\le C_j$, set $H=j$; otherwise set $L=j+1$.
3. When $L=H$, return outcome $L$.

Thus on positive inputs the intended output is the least index with $v\le C_i$, including equality at a cumulative threshold. For $0<U<1$, this is the generalized inverse of the step CDF $F(i)=C_i$ by Generalized inverse sublevel identity for a CDF. At $v=1$, the same least-index rule specifies the endpoint extension $\min \{i:C_i=1\}$; this set contains $r$. The midpoint and ideal-input law and binary-search properties are proved separately.

With ideal $U$, this is exact finite categorical inversion. Midpoint input has a discrete law; its threshold counts, rather than total-variation closeness to a continuous uniform law, control its categorical error.