title: Efficient way to search an element
body: <p>Recently I had an interview, where they asked me a "<em>searching</em>" question.<br>
  The question was:</p>
  
  <blockquote>
    <p>Assume there is an array of (positive) integers, of which each element is either <code>+1</code> or <code>-1</code> compared to its adjacent elements.</p>
    
    <p><strong>Example:</strong></p>
  
  <pre><code>array = [4,5,6,5,4,3,2,3,4,5,6,7,8];
  </code></pre>
    
    <p>Now search for <code>7</code> and return its position.</p>
  </blockquote>
  
  <p>I gave this answer:</p>
  
  <blockquote>
    <p>Store the values in a temporary array, sort them, and then apply binary search.</p>
    
    <p>If the element is found, return its position in the temporary array.<br>
    (If the number is occurring twice then return its first occurrence)</p>
  </blockquote>
  
  <p>But, they didn't seem to be satisfied with this answer.</p>
  
  <p>What is the right answer?</p>