First occurrence in a binary search

Question

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 first occurrence? Is this something people do?

//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 <= high) {         int mid = (low + high) >>> 1;         long midVal = a[mid].val;          if (midVal < key)             low = mid + 1;         else if (midVal > key)             high = mid - 1;         else             return mid; // key found     }     return (low); // key not found. return insertion point } 

Answer 1

An addition to Jon Skeets post:

The potential faster implementation is actually not hard to implement and adds only 2 lines of code, here is how I'd do it:

    if (midVal < key)         low = mid + 1;     else if (midVal > key)         high = mid - 1;     else if (low != mid) //Equal but range is not fully scanned         high = mid; //Set upper bound to current number and rescan     else //Equal and full range is scanned         return mid;