title: efficiently find amount of integers in a sorted array
body: <p>I'm studying for a test, and found this question.</p>
  
  <p>You are given a sorted array of integers for example:</p>
  
  <pre><code>{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}
  </code></pre>
  
  <p>Write a method:</p>
  
  <pre><code>Public static int count (int[] a, int x)
  </code></pre>
  
  <p>that returns the amount of times, number 'x' is in the array.</p>
  
  <p>for example:</p>
  
  <pre><code>x = -5, it returns 2
  x = 2, it returns 5
  x = 8, it returns 0
  </code></pre>
  
  <p>I need to write it as efficient as possible, please don't give me the answer
  (or write it if you wish, but I won't look), my idea is to do a binary search, and then
  go both edges (backward and forward) of the value that I find and with the index numbers, return the correct answer, my questions are:</p>
  
  <ol>
  <li>is it the most efficient way?</li>
  <li>won't it be O(n) in the worst case? (when the array is filled with a single number) -</li>
  </ol>
  
  <p>If so - then why should I do a binary search? </p>