16

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

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

我知道我也可以使用二进制搜索手动执行此操作，但我想知道是否已经有一个库或集合在执行此操作。

4

6 回答 6

11

你有两个选择：

于 2010-05-31T17:25:07.847 回答
7

到目前为止（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));
}
于 2016-09-26T11:49:57.293 回答
3

只是为了完整起见，这里有一个小的 java 函数，可以将输出 fromArrays.binarySearch转换为接近输出 from 的东西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;
}
于 2015-07-27T03:19:02.377 回答
2

为什么不对久经考验的 Python 代码本身进行快速移植呢？例如，这是一个 Java 端口bisect_right：

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; 
}
于 2017-08-06T18:16:35.873 回答
1

基于java.util.Arrays.binarySearch 文档

在这里，我将示例用于long[]数组，但可以调整代码以利用任何受支持的类型。

int bisectRight(long[] arr, long key) {
    int index = Arrays.binarySearch(arr, key);
    return Math.abs(index + 1);
}

注意：Java API 的限制，来自 javadoc 的以下句子：

If the array contains multiple elements with the specified value,
there is no guarantee which one will be found

事实上，我已经用不同元素的排序数组进行了测试。我的用例是用于范围分组，其中arr一组不同的时间戳表示间隔的开始时间。

于 2021-09-07T14:15:59.823 回答
0

您需要自己定义，这是我的：

bisect.bisect_left

public static int bisectLeft(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i <= j) {
        int m = i + (j-i) / 2;
        if (nums[m] >= target) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i;
}

bisect.bisect_right

public static int bisectRight(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i <= j) {
        int m = i + (j-i) / 2;
        if (nums[m] <= target) {
            i = m + 1;
        } else {
            j = m - 1;
        }
    }
    return j+1;
}
于 2021-12-24T14:34:13.597 回答