Use binary search on the prefix array to find the smallest index where prefix[index] > r.
Example: if r = 2.5 and prefix = [1, 4, 6], binary search finds index 1 (since prefix[1] = 4 > 2.5).
This ensures index 1 is picked 3 times as often as index 0, matching the weights.