Solution: Random Pick with Weight
Discover how to perform weighted random selection by converting weights into running sums and applying modified binary search. Understand the differences between naive linear search and an optimized binary search approach to efficiently pick indices based on probability weights. This lesson helps you grasp key algorithmic concepts for solving random weighted selection problems with optimal performance.
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:
-
Index 2: ...