Java 中 bisect 的等价方法

Question

在Java中有没有类似于Python的bisect模块的东西？Python的bisect可以用来对数组进行二分查找，并且可以指定方向。例如，bisect.bisect_left的功能是：

找到一个合适的位置，把某个元素插入到列表中，以保持列表的顺序。参数lo和hi可以用来指定要考虑的列表的一个子集；默认情况下，会使用整个列表。

我知道我也可以通过二分查找手动实现这个功能，但我想知道是否已经有现成的库或工具可以做到这一点。

Answer 1

为了完整性，这里有一个小的Java函数，它将Arrays.binarySearch的输出转换成类似于bisect_left的结果。虽然我显然还有很多地方没考虑到，但这个函数对于简单的情况是可以工作的。

public static int bisectLeft(double[] a, double key) {
    int idx = Math.min(a.length, Math.abs(Arrays.binarySearch(a, key)));
    while (idx > 0 && a[idx - 1] >= key) idx--;
    return idx;
}

Answer 2

到现在为止（Java 8），这个功能还是没有，所以你还是得自己写一个。下面是我写的：

public static int bisect_right(int[] A, int x) {
    return bisect_right(A, x, 0, A.length);
}

public static int bisect_right(int[] A, int x, int lo, int hi) {
    int N = A.length;
    if (N == 0) {
        return 0;
    }
    if (x < A[lo]) {
        return lo;
    }
    if (x > A[hi - 1]) {
        return hi;
    }
    for (;;) {
        if (lo + 1 == hi) {
            return lo + 1;
        }
        int mi = (hi + lo) / 2;
        if (x < A[mi]) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
}

public static int bisect_left(int[] A, int x) {
    return bisect_left(A, x, 0, A.length);
}

public static int bisect_left(int[] A, int x, int lo, int hi) {
    int N = A.length;
    if (N == 0) {
        return 0;
    }
    if (x < A[lo]) {
        return lo;
    }
    if (x > A[hi - 1]) {
        return hi;
    }
    for (;;) {
        if (lo + 1 == hi) {
            return x == A[lo] ? lo : (lo + 1);
        }
        int mi = (hi + lo) / 2;
        if (x <= A[mi]) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
}

我在这里测试了（X是我用来存放那些我想重复使用的静态方法的类）：

@Test
public void bisect_right() {
    System.out.println("bisect_rienter code hereght");
    int[] A = new int[]{0, 1, 2, 2, 2, 2, 3, 3, 5, 6};
    assertEquals(0, X.bisect_right(A, -1));
    assertEquals(1, X.bisect_right(A, 0));
    assertEquals(6, X.bisect_right(A, 2));
    assertEquals(8, X.bisect_right(A, 3));
    assertEquals(8, X.bisect_right(A, 4));
    assertEquals(9, X.bisect_right(A, 5));
    assertEquals(10, X.bisect_right(A, 6));
    assertEquals(10, X.bisect_right(A, 7));
}

@Test
public void bisect_left() {
    System.out.println("bisect_left");
    int[] A = new int[]{0, 1, 2, 2, 2, 2, 3, 3, 5, 6};
    assertEquals(0, X.bisect_left(A, -1));
    assertEquals(0, X.bisect_left(A, 0));
    assertEquals(2, X.bisect_left(A, 2));
    assertEquals(6, X.bisect_left(A, 3));
    assertEquals(8, X.bisect_left(A, 4));
    assertEquals(8, X.bisect_left(A, 5));
    assertEquals(9, X.bisect_left(A, 6));
    assertEquals(10, X.bisect_left(A, 7));
}

Answer 3

你有两个选择：

• java.util.Arrays.binarySearch 用于数组
  • (有不同类型数组的多种重载方式)
• java.util.Collections.binarySearch 用于 List
  • (有 Comparable 和 Comparator 的重载).
  • 可以结合使用 List.subList(int fromIndex, int toIndex) 来搜索列表的一部分