如何在 Java 中实现 lower_bound 二进制搜索算法？

Question

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

我看java.util.Arrays.binaySearchsource code

我发现了一些评论：

If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

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

注意：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

基于对另一个二进制搜索问题的回答：

How can I simplify this working Binary Search code in C?

这是等同于 C++ 中的 lower_bound 的搜索。它returns小于你要查找的值的元素个数。那将是第一次出现的索引，或者如果没有出现将插入的位置：

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);
                }
}

如何在 Java 中实现 lower_bound 二进制搜索算法？

How to implement a lower_bound binary search algorithm in Java?

java

algorithm

binary-search