# Algorithm to find numerical bucket in dynamic list

## Algorithm to find numerical bucket in dynamic list

Contents

Problem Description:

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?

## Solution – 1

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)

Rate this post
We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.