問題描述

我正在修改一些代碼，但我意識到了一些我從來不知道的事情.正常的二分搜索將在數(shù)據(jù)集中為多次出現(xiàn)的鍵返回隨機(jī)索引.如何修改下面的代碼以返回第一次出現(xiàn)?這是人們做的事情嗎?

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
}

推薦答案

找到一個(gè)匹配的值，你基本上需要遍歷集合，直到找到一個(gè)沒有的條目 匹配.

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

您可以潛在地通過立即獲取低于您要查找的鍵的索引來使其更快，然后在兩者之間進(jìn)行二進(jìn)制切割 - 但我可能會(huì)選擇更簡單的版本，除非您有大量相等的條目，否則它可能足夠高效".

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.

這篇關(guān)于二分查找中的第一次出現(xiàn)的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！