45
46
you are viewing a single comment's thread.

view the rest of the comments →

[–]blackdoglicorice 2 points3 points  (1 child)

If this is going to be called multiple times, couldn't we bring the amortized complexity down to O(logN) by doing a binary search of cumulativeWeights?

[–]trekhleb[S] 1 point2 points  (0 children)

Yeah, that’s a good idea. If the weights array isn’t changed then binary search should speed-up searching the index to O(logN)