title: How to find all "feasible" values in an array in O(nlogn) and O(n)?
body: <p>Suppose we are given a "black-box" which is a program procedure such that given any real
  number x as the input, the procedure can tell whether x is a feasible value in constant time.
  Further, we have the following basic rules: If x is a feasible value, then any number less
  than x is also a feasible value; on the other hand, if x is not a feasible value, then any number
  larger than x is not a feasible value.
  Given an array A[1,..., n] of n real numbers, we want to find all feasible values of the
  elements of A by using the black-box. For each element x of A, we can call the black-box on
  x to determine whether x is feasible value. In this way, by calling the black-box n times, we can find all feasible values of A in O(n) time. However, by making use of the above basic
  rules, it is possible to find all feasible values of A by calling the black-box significantly less
  than n times. For simplicity, we assume that no two numbers of A are equal.</p>
  
  <p>1) first I want to design an O(n log n) time algorithm to find all feasible values of A by calling the black-
  box at most O(log n) times.</p>
  
  <p>2) then I want to improve my algorithm to O(n) time such that the total number of calls on the black-
  box is still at most O(log n).</p>
  
  <p>So far I have designed an algorithim inspired by the prune and search algorithm and selection:</p>
  
  <pre><code>findFeasible(A, blackBox)
  {
  randomly pick an element of A as the pivot (p);
  A1: the set of elements &lt; p;
  A2: the set of elemetns &gt; p;
  out = blackBox(p);
  if out == feasible
           return p, A1;
           findFeasible(A2, blackBox);
  if out != feasible
           findFeasible(A1, blackBox);
  </code></pre>
  
  <p>But I'm not sure what is the timing for this algorithm I wrote and what could be done to improve.</p>