title: Pseudocode for simple range search algorithm
body: <p>I am working through some practise problem sets for an upcoming CS exam. I was hoping I could get some help figuring out pseudocode for this algorithm:</p>
  
  <blockquote>
    <p>Given an array of <code>n</code> integers that have been sorted in increasing order, I need to give a pseudocode description of an algorithm to perform a range search on A having complexity <code>O(r + logn)</code>, where <code>r</code> is the number of outputted points. In other words, given a closed interval <code>[lo, hi]</code>, output all the array elements <code>A[i]</code> where <code>lo &lt;= A[i] &lt;= hi</code>.</p>
  </blockquote>
  
  <hr>
  
  <p>I understand that the '<code>r</code>' portion of the complexity will simply be outputting the elements which are within the interval (having placed them in a separate array in the algorithm).</p>
  
  <p>I am not quite sure how to do this. It is suppose to be just one algorithm. Is recursion necessary? Since the algorithm has to be <code>log(n)</code>, dividing the array constantly seems like an idea. I am just confused on how to implement it.</p>