Binary Search for Discrete Sampling - Interactive Simulation

Interactive visualization of the inverse CDF method using binary search — guaranteed O(log K) performance

⚙️ Controls

Distribution Shape (K=16)

Like Binomial(15, 0.5) — single peak in the middle

Random Uniform Value

—

📊 PMF Shape

📋 PMF & CDF Table (rounded)

k	p(k)	F(k)

📈 CDF Step Function

🌳 Binary Search Tree

Categories (K)

Steps Taken

At Most (⌈log₂K⌉)

—

Result (k)

🔎 Search Trace

// Invariant: answer ∈ [low, high]

low ← 1, high ← 16

Click "New Search" to begin

💡 The Binary Search Invariant

Goal: Find the least k with F(k) ≥ U — equivalent to a lower_bound search on the CDF staircase.

Invariant: The answer is always in [low, high]. Each step halves this interval.

🎯 Minimax Guarantee

Binary search minimizes the maximum cost. No matter where U falls, we complete in at most ⌈log₂ K⌉ steps. For K=16, that's ≤ 4 steps.

🔍 Binary Search for Discrete Sampling