title: Finding even numbers in an array without using feedback
body: <p>I saw this post: <a href="https://stackoverflow.com/questions/8582959/finding-even-numbers-in-an-array/8584598">Finding even numbers in an array</a> and I was thinking about how you could do it without feedback. Here's what I mean.</p>
  
  <blockquote>
    <p>Given an array of length n containing at most <code>e</code> even numbers and a
    function <code>isEven</code> that returns true if the input is even and false
    otherwise, write a function that prints all the even numbers in the
    array using the fewest number of calls to <code>isEven</code>.</p>
  </blockquote>
  
  <p>The answer on the post was to use a binary search, which is neat since it doesn't mean the array has to be in order. The number of times you have to check if a number is even is <code>e log n</code> instead if <code>n</code> because you do a binary search (<code>log n</code>) to find one even number each time (<code>e</code> times). </p>
  
  <p>But that idea means that you divide the array in half, test for evenness, then decide which half to keep based on the result.</p>
  
  <p>My question is whether or not you can beat <code>n</code> calls on a fixed testing scheme where you check all the numbers you want for evenness without knowing the outcome, and then figure out where the even numbers are after you've done all the tests based on the results. So I guess it's no-feedback or blind or some term like that.</p>
  
  <p>I was thinking about this for a while and couldn't come up with anything. The binary search idea doesn't work at all with this constraint, but maybe something else does? Even getting down to <code>n/2</code> calls instead of <code>n</code> (yes, I know they are the same big-O) would be good.</p>