Solution: Random Pick with Weight
Explore how to select a weighted random index from an array by creating running sums of weights and applying a binary search to find the appropriate index quickly. This lesson helps you understand both a naive linear search approach and an optimized binary search for efficient weighted random selection.
Statement
You’re given an array of positive integers, weights, where weights[i] is the weight of the index.
Write a function, Pick Index(), which performs weighted random selection to return an index from the weights array. The larger the value of weights[i], the heavier the weight is, and the higher the chances of its index being picked.
Suppose that the array consists of the weights . In this case, the probabilities of picking the indexes will be as follows:
-
Index 0:
-
Index 1: ...