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

Question

假设我们有一个"黑盒子"，它是一个程序过程，给定任何实数数字x作为输入，程序可以判断x在常数时间内是否可行。进一步，我们有以下基本规则:如果x是可行值，则任意数小于那么x也是可行值;另一方面，如果x不是可行值，则任意数大于x是不可行的值。给定数组A[1，…]， n] (n个实数)我们想要find所有可行的值A的元素用黑盒表示。对于A中的每个元素x，我们可以调用黑盒来判断X是否为可行值。这样，通过调用黑箱n次，我们可以在O(n)时间内找到A的所有可行值。然而，通过利用上述基本规则，可以通过调用黑盒significantly less找到A的所有可行值比n倍。为简单起见，我们假设A的两个数不相等。

1)首先，我想设计一个O(n log n)时间算法，通过调用黑-来find A的所有可行值最多O(log n)次。

2)，那么我想把我的算法改进到O(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

For 2)

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

每次运行快速选择时，将长度除以2。所以总成本是

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

对黑匣子执行O(log n)次呼叫

Answer 2

For 1):

在O(n*log(n))时间内对数组进行排序。然后进行二叉搜索，找到将数组分成下半部分(可行值)和上半部分(不可行的值)的元素的索引。二叉搜索耗时O(log(n))