如何在 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) {&nbsp; &nbsp; int min = 0;&nbsp; &nbsp; int max = sequence.length - 1;&nbsp; &nbsp; int result = -1;&nbsp; &nbsp; while (min <= max)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; // find the mid value and compare it with x&nbsp; &nbsp; &nbsp; &nbsp; int mid = min + ((max - min) / 2);&nbsp; &nbsp; &nbsp; &nbsp; // if x is found, update result and search towards left&nbsp; &nbsp; &nbsp; &nbsp; if (x == sequence[mid]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = mid;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = mid - 1;&nbsp; &nbsp; &nbsp; &nbsp; } else if (x < sequence[mid]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // discard right half&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = mid - 1;&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // discard left half&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = mid + 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // return the leftmost index equal to x or -1 if not found&nbsp; &nbsp; return result;}编辑：更改计算 mid 的方式以避免较大总和溢出// Previously, can overflow since we add two integerint mid = (min + max) / 2;// Nowint mid = min + ((max - min) / 2);// Another way using the unsigned right shift operatorint 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

这是相当于lower_boundC++ 的搜索。它返回小于您要查找的值的元素数量。这将是第一次出现的索引，或者如果没有出现则将插入其中：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){&nbsp; &nbsp; if(low>high){&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Target not found");&nbsp; &nbsp; &nbsp; &nbsp; return false;}&nbsp; &nbsp; &nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int mid=(low+high)/2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(target==data[mid])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if(target<data[mid])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binarysearch(data, target, low, high);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binarysearch(data, target, low, high);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }}