任意概率分布的随机数发生器

Question

这里是极客健忘的解决方案。我无法理解findCeil()部分。步骤4.在前缀数组中查找在步骤3中生成的随机数的Ceil索引。将索引设为索引c。

// Utility function to find ceiling of r in arr[l..h]
int findCeil(int arr[], int r, int l, int h)
{
    int mid;
    while (l < h)
    {
         mid = l + ((h - l) >> 1);  // Same as mid = (l+h)/2
        (r > arr[mid]) ? (l = mid + 1) : (h = mid);
    }
    return (arr[l] >= r) ? l : -1;
}

有人能解释一下正在做什么吗。

Answer 1

它正在执行数组的二进制搜索，以找到值大于r的数组的第一个元素。

编辑：下面是一个示例搜索的动画