arrays - 如何在 O(nlogn) 和 O(n) 的数组中找到所有 "feasible"值？

Question

假设我们有一个“黑匣子”，它是一个程序过程，给定任何真实的数字 x 作为输入，该过程可以判断 x 是否是常数时间内的可行值。进一步，我们有以下基本规则:如果 x 是一个可行的值，则比 x 也是可行值；另一方面，如果 x 不是可行值，则任何数大于 x 不是可行值。给定一个包含 n 个实数的数组 A[1,..., n]，我们想要找到所有可行的值A 的元素通过使用黑盒。对于 A 的每个元素 x，我们可以调用黑盒x 判断 x 是否为可行值。这样，通过调用黑盒 n 次，我们可以在 O(n) 时间内找到 A 的所有可行值。但是，通过使用上述基本规则，可以通过显着减少调用黑盒来找到 A 的所有可行值比n倍。为简单起见，我们假设 A 中没有两个数是相等的。

1) 首先我想设计一个时间复杂度为 O(n log n) 的算法，通过调用 black-框最多 O(log n) 次。

2) 然后我想将我的算法改进到 O(n) 时间，这样黑色的调用总数-box 仍然至多为 O(log n)。

到目前为止，我已经设计了一个受修剪和搜索算法和选择启发的算法:

findFeasible(A, blackBox)
{
randomly pick an element of A as the pivot (p);
A1: the set of elements < p;
A2: the set of elemetns > p;
out = blackBox(p);
if out == feasible
         return p, A1;
         findFeasible(A2, blackBox);
if out != feasible
         findFeasible(A1, blackBox);

但是我不确定我写这个算法的时机是什么时候以及可以做些什么来改进。

Answer 1

对于 2)

使用 quickselect 在 O(n) 中找到数组的中位数.检查中位数是否可行。如果是，则在数组的左半部分递归运行该算法。如果不是，则运行右侧的算法。

每次运行快速选择时，都会将长度除以 2。因此，总成本将为

O(n) + O(n/2) + O(n/4) + O(n/8) ... = O(n)

对黑盒执行 O(log n) 次调用。