如何用Java实现lower_bound二分查找算法？

Question

我想找到一个目标值4在序列[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6]中第一次出现的位置。当我使用 java.util.Arrays.binaySearch 时，它返回索引是 9，但我期望的是 7。

我看java.util.Arrays.binaySearch 源代码

我发现了一些评论：

如果数组包含多个具有指定值的元素，则不保证会找到哪一个。

那么如何在Java中实现一个lower_bound二分查找算法，返回目标值首先出现的地方。

注意：lower_bound概念来自C++，但我不太了解C++。

Answer 1

我认为下面的实现将正确完成工作：

int firstOccurrence(int[] sequence, int x) {
    int min = 0;
    int max = sequence.length - 1;

    int result = -1;

    while (min <= max)
    {
        // find the mid value and compare it with x
        int mid = min + ((max - min) / 2);

        // if x is found, update result and search towards left
        if (x == sequence[mid]) {
            result = mid;
            max = mid - 1;
        } else if (x < sequence[mid]) {
            // discard right half
            max = mid - 1;
        } else {
            // discard left half
            min = mid + 1;
        }
    }

    // return the leftmost index equal to x or -1 if not found
    return result;
}

编辑：

更改计算 mid 的方式以避免较大总和溢出

// Previously, can overflow since we add two integer
int mid = (min + max) / 2;

// Now
int mid = min + ((max - min) / 2);

// Another way using the unsigned right shift operator
int mid = (low + high) >>> 1;
// The left operands value (low + high) is moved right
// by the number of bits specified (2 in this case) by the right operand and
// shifted values are filled up with zeros.
// The >>> treats the value as unsigned

Answer 2

基于另一个二分搜索问题的答案：

如何简化 C 语言中的二进制搜索代码？

这是相当于 C++ 中的

lower_bound

的搜索。它返回小于您要查找的值的元素数量。那将是 第一次出现的索引，或者如果没有出现则插入的位置：

int numSmaller(int[] seq, int valueToFind)
{
    int pos=0;
    int limit=seq.length;
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (seq[testpos]<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    return pos;
}

请注意，每次迭代我们只需要进行一次比较。

链接的答案强调了以这种方式编写二分搜索的几个优点。

Answer 3

相信会对你有帮助

public static boolean binarysearch(int[] data, int target, int low, int high){
    if(low>high){
        System.out.println("Target not found");
        return false;}
        else{
                int mid=(low+high)/2;
                if(target==data[mid])
                    return true;
                else if(target<data[mid])
                    return binarysearch(data, target, low, high);
                else
                    return binarysearch(data, target, low, high);
                }
}

Answer 4

您可以使用 Arrays.binarySearch() 在 C++ 中实现 lower_bound。

        int index=Arrays.binarySearch(array,0,len,target);
        index=index>=0 ? index : -index-1;