title: Find any one of multiple possible repeated integers in a list
body: <p>Given an array of <code>n+1</code> integers, each in the range <code>1</code> to <code>n</code>, find an integer that is repeated. </p>
  
  <p>I was asked this at a job interview. Here's my answer: The Pigeonhole Principle says there has to be a repeat. I tried to use a binary search approach, so I did this in Matlab, because that's what I know:</p>
  
  <pre><code>top = 0;
  bot = 0;
  for i=1:n+1
    if P[i] &gt; n/2 
      top = top+1;
    else
      bot = bot+1;
  end
  </code></pre>
  
  <p>So then I argue that one of these, <code>top</code> or <code>bot</code>, has to be bigger than <code>n/2</code> by the PhP again. Take that range and repeat.</p>
  
  <p>I thought this was a pretty good solution, but the interviewer sort of hinted that one can do better. Please post any better solutions you know of.</p>