有没有更快的方法通过累积分布搜索？

Question

我有一个列表 ，其中包含对项目进行抽样的概率（权重）。例如，列表包含如下所示的5个值。

我尝试了这样的方法，首先把概率列表做成累加形式。

0.1、0.5、0.7、0.8、1.0

那么我的做法如下。我生成一个随机double，并在列表上迭代以找到第一个大于随机double的项，然后返回它的索引。

Random r = new Random();
double p = r.nextDouble();
int total = list.size();
for(int i=0; i < total; i++) {
 double d = list.get(i);
 if(d > p) {
  return i;
 }
}
return total-1;

我不确定二分搜索能有什么帮助。假设我生成了p=0.01。然后，二分搜索可以使用递归，如下所示。

compare 0.01 to 0.7, repeat with L = 0.1, 0.5
compare 0.01 to 0.1, stop 
compare 0.01 to 0.5, stop

0.01小于0.7、0.5和0.1，但我显然只想要0.1。因此，当使用二分搜索时，停止条件对我来说仍然不清楚。

如果有一个图书馆来帮助这类事情，我也很感兴趣。

Answer 1

以下是如何使用二分搜索，从累积概率开始：

public static void main (String[] args) {
    double[] cdf = {0.1, 0.5, 0.7, 0.8, 1.0};
    double random = 0.75;  // generate randomly between zero and one
    int el = Arrays.binarySearch(cdf, random);
    if (el < 0) {
        el = -(el + 1);
    }
    System.out.println(el);
}

附言。当概率列表很短时，简单的线性扫描可能会证明与二分搜索一样有效。