## Algorithm to find numerical bucket in dynamic list

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)