二进制搜索中的首次出现

algorithm binary-search java search binary

2022-09-01 16:22:28

我正在修改一些代码，我意识到了一些我从来不知道的事情。正常的二进制搜索将在数据集中为多次出现的键返回随机索引。如何修改下面的代码以返回第一次出现？这是人们做的事情吗？

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

答案 1

对Jon Skeets帖子的补充：

潜在的更快的实现实际上并不难实现，并且只添加了2行代码，以下是我的做法：

    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;

答案 2

找到匹配的值后，您基本上需要向上浏览集合，直到找到不匹配的条目。

你可以通过获取一个键的索引来使它更快，然后从两者之间进行二进制切分 - 但我可能会选择更简单的版本，除非你有非常多的相等条目，否则它可能是“足够有效的”。