二分查找中的第一次出现

问题描述

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

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
}

推荐答案

找到一个匹配的值，你基本上需要遍历集合，直到找到一个没有的条目 匹配.

Having found a matching value, you basically need to walk up the collection until you find an entry which doesn't match.

您可以潜在地通过立即获取低于您要查找的键的索引来使其更快，然后在两者之间进行二进制切割 - 但我可能会选择更简单的版本，除非您有大量相等的条目，否则它可能足够高效".

You could potentially make it faster by fetching the index of a key immediately lower than the one you were looking for, then do a binary chop between the two - but I'd probably go for the simpler version, which is likely to be "efficient enough" unless you've got a really large number of equal entries.

这篇关于二分查找中的第一次出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！