首次出现在二分查找中

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

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;

Answer 2

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

你可以潜在地使其更快通过获取一键立即比你正在寻找一个较低的指数,然后做两者之间的二进制印章-但我可能会去的简单版本,这很可能是"高效足够的"除非你有相当多的平等条目.

Answer 3

如果您的数据都是完整的，那么这个技巧可以提供帮助。它使用浮点数组来存储值。

float array[];    //contains all integral values
int searchValue;

int firstIndex = -(binarySearch(array, (float)searchValue - 0.5F) + 1);

基本上，它的作用是找到搜索值与其之前的整数之间的值的插入索引。由于所有值都是整数，因此它会找到搜索值的第一次出现。

而且这个运行时间是log(n)。

例子：

import java.util.Arrays;

public class BinarySearch {
    // considering array elements are integers
    float ar[] = new float[] { 1, 2, 3, 3, 4, 4, 5, 9, 9, 12, 12 };

    public void returnFirstOccurrence(int key) {
        int firstIndex = -(Arrays.binarySearch(ar, key - 0.5F) + 1);
        if (ar[firstIndex] != key)
            System.out.println("Key doesn't exist");
        else
            System.out.println("First index of key is " + firstIndex);
    }

    public static void main(String Args[]) throws Exception {
        new BinarySearch().returnFirstOccurrence(9);
    }

}

输出：7

ps：我在几次编码比赛中使用过这个技巧，每次都很有效。