如何在 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++ 进行的搜索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);

                }

}