16

Java で Python のbisect モジュールに相当するものはありますか? Python の bisect を使用すると、方向を指定して配列の二分を行うことができます。たとえば、次のようbisect.bisect_leftにします。

リスト内のアイテムの適切な挿入ポイントを見つけて、並べ替え順序を維持します。パラメータ lo と hi を使用して、考慮すべきリストのサブセットを指定できます。デフォルトでは、リスト全体が使用されます。

二分探索でもこれを手動で実行できることはわかっていますが、これを実行しているライブラリまたはコレクションが既に存在するかどうか疑問に思っていました。

4

6 に答える 6

11

次の 2 つのオプションがあります。

于 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

完全を期すために、 からArrays.binarySearchの出力を からの出力に近いものに変換する小さな Java 関数を次に示します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 に答える