title: First occurrence in a binary search
body: <p>I'm tinkering with some code and I realized something I never knew.  A normal binary search will return a random index in a data set for a key that occurs more than once.  How can I modify this code below to return the <em>first occurrence</em>?  Is this something people do?</p>
  
  <pre><code>//ripped from the JDK
  public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
      return bSearchVal(a, 0, a.length, key);
  }
  
  private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                                   int toIndex, long key) {
      int low = fromIndex;
      int high = toIndex - 1;
  
      while (low &lt;= high) {
          int mid = (low + high) &gt;&gt;&gt; 1;
          long midVal = a[mid].val;
  
          if (midVal &lt; key)
              low = mid + 1;
          else if (midVal &gt; key)
              high = mid - 1;
          else
              return mid; // key found
      }
      return (low); // key not found. return insertion point
  }
  </code></pre>