我正在调试一些代码,然后发现了一个以前不知道的事情。普通的二分查找会在数据集中返回一个键出现多次的随机索引。我如何修改下面的代码以返回第一个出现的位置?这是人们经常做的吗?
//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
}