Java相当于python中的bisect

Question

Java的bisect模块中是否有Java的等价物？使用Python的bisect,您可以使用方向进行数组二分.例如bisect.bisect_left:

找到列表中项目的正确插入点以维护排序顺序.参数lo和hi可用于指定应考虑的列表的子集; 默认情况下,使用整个列表.

我知道我也可以通过二进制搜索手动执行此操作,但我想知道是否已有一个库或集合执行此操作.

Answer 1

您有两种选择:

• java.util.Arrays.binarySearch 在数组上
  • (针对不同数组类型的各种重载)
• java.util.Collections.binarySearch 上 List
  • (有Comparable和Comparator超载).
  • 结合List.subList(int fromIndex, int toIndex)搜索列表的一部分

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