二进制搜索中的首次出现

Question

我正在修改一些代码，但我意识到一些我不知道的东西。普通的二进制搜索将在数据集中为出现多次的键返回随机索引。如何修改下面的代码以返回第 一次出现的
代码？人们会这样做吗？

//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

在找到 一个 匹配值，你基本上需要，直到你找到它的入口走了集合 不 匹配。

您可以通过获取刚好低于您要查找的键的索引，然后在两者之间进行二进制剁碎， 从而
使速度更快，但是我可能会选择更简单的版本，这可能“很有效”。足够”，除非您有大量相等的条目。