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
}
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;