Say I have input that looks something like this:
[
{index: 0, probability: 0.20},
{index: 1, probability: 0.10},
{index: 2, probability: 0.40},
{index: 3, probability: 0.25},
{index: 4, probability: 0.05},
]
Given that I generate a random number [0,1), is there an O(1) algorithm that I can use to find which index of this array "matches" that probability?
The way I would do it in O(N) is to do something like:
let cumulative = 0;
const r = Math.random();
for(const v of list){
cumulative = v.probability;
if(r < cumulative){
return v.index;
}
}
I believe the O(N) algorithm is doing what I want, but not sure if there is a faster way?
CodePudding user response:
Replace the list with cumulative probability:
[
{index: 0, probability: 0.20},
{index: 1, probability: 0.30},
{index: 2, probability: 0.70},
{index: 3, probability: 0.95},
{index: 4, probability: 1.00},
]
Then do a binary search on probability to find the index. The complexity would be O(log N)