title: Find the first element in a sorted array that is greater than the target
body: <p>In a general binary search, we are looking for a value which appears in the array. Sometimes, however, we need to find the first element which is either greater or less than a target.</p>
  
  <p>Here is my ugly, incomplete solution:</p>
  
  <pre class="lang-c prettyprint-override"><code>// Assume all elements are positive, i.e., greater than zero
  int bs (int[] a, int t) {
    int s = 0, e = a.length;
    int firstlarge = 1 &lt;&lt; 30;
    int firstlargeindex = -1;
    while (s &lt; e) {
      int m = (s + e) / 2;
      if (a[m] &gt; t) {
        // how can I know a[m] is the first larger than
        if(a[m] &lt; firstlarge) {
          firstlarge = a[m];
          firstlargeindex = m;
        }
        e = m - 1; 
      } else if (a[m] &lt; /* something */) {
        // go to the right part
        // how can i know is the first less than  
      }
    }
  }
  </code></pre>
  
  <p>Is there a more elegant solution for this kind of problem? </p>