Java在python中相当于等分

Is there a java's equivalent to python's bisect library? With python's bisect you can do array bisection with directions. For instance bisect.bisect_left does:

是否有一个java等效于python的bisect库?使用python的二等分，可以用方向来做数组二等分。例如平分。bisect_left:

Locate the proper insertion point for item in list to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used.

在列表中找到适当的插入点以维持排序顺序。参数lo和hi可用于指定应考虑的列表的子集;默认情况下使用整个列表。

Note: Sure of course i now i can do this manually with a binary search too, but wondered if there is already a lib or collection doing this.

注意:当然，我现在也可以手动进行二分查找，但不知道是否已经有一个lib或collection在做这个。

4 个解决方案

#1

You have two options:

你有两个选择:

java.util.Arrays.binarySearch on arrays
- (with various overloads for different array types)
- (不同数组类型有不同的重载)
java.util.Arrays。数组上的binarySearch(对于不同的数组类型有不同的重载)
java.util.Collections.binarySearch on List
- (with Comparable and Comparator overloads).
- (具有可比性和比较器过载)。
- Combine with List.subList(int fromIndex, int toIndex) to search portion of a list
- 结合列表。子列表(int fromIndex, int toIndex)以搜索列表的一部分
java.util.Collections。列表上的binarySearch(具有可比和比较器重载)。结合列表。子列表(int fromIndex, int toIndex)以搜索列表的一部分

#2

Just for completeness, here's a little java function that turns the output from Arrays.binarySearch into something close to the output from bisect_left. I'm obviously missing things, but this does the job for the simple case.

为了完整起见，这里有一个小java函数，可以从数组中转换输出。将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;
}

#3

To this date (Java 8), this is still missing, so you must still make your own. Here's mine:

到目前为止(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;
        }
    }
}

Tested with (X being the class where I store static methods that I intend to reuse):

使用(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));
}

#4

Why not do a quick port of the tried and tested Python code itself? For example, here's a Java port for bisect_right:

为什么不快速地移植经过测试的Python代码本身呢?例如，这是bisect_right的Java端口:

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

private static int bisect_right(double[] A, double x, int lo, int hi) {
  while (lo < hi) {
    int mid = (lo+hi)/2; 
    if (x < A[mid]) hi = mid; 
    else lo = mid+1;
  }
  return lo; 
}

#1