这是geeksforgeeks解决方案。我无法理解findCeil()部分。第 4 步。在前缀数组中查找步骤 #3 中生成的随机数的 Ceil 索引。让索引成为索引。
// 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;
}
有人可以解释一下正在做什么吗?
它正在对数组执行二进制搜索,以查找值大于 r 的数组的第一个元素。维基文章应该很好地解释这项技术。
编辑:下面是示例搜索的动画