Java эквивалент bisect в python

Существует ли эквивалент java для библиотеки bisect python? С помощью bisect python вы можете выполнять разделение массива с помощью направлений. Например, bisect.bisect_left делает:

Найдите правильную точку вставки для элемента в списке, чтобы сохранить отсортированный порядок. Параметры lo и hi могут использоваться для указания подмножества списка, который следует учитывать; по умолчанию используется весь список.

Примечание: Конечно, теперь я могу сделать это вручную с помощью двоичного поиска, но задался вопросом, есть ли уже коллекция lib или collection.

Ответ 1

У вас есть два варианта:

java.util.Arrays.binarySearch на массивах
- (с различными перегрузками для разных типов массивов)
java.util.Collections.binarySearch на List
- (с Comparable и Comparator перегрузки).
- Объедините с List.subList(int fromIndex, int toIndex) для поиска части списка

Ответ 2

Просто для полноты здесь немного 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;
}

Ответ 3

К этой дате (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));
}

Ответ 4

Почему бы не сделать быстрый порт проверенного и проверенного самого кода 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; 
}