Java jest odpowiednikiem bisect w pythonie

Question

Czy jest odpowiednik biblioteki półtonów pythona? Przy pomocy bitu Pythona możesz zrobić podział bisekcji za pomocą wskazówek. Na przykład bisect.bisect_left robi:

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.

Uwaga: Jasne, oczywiście ja teraz mogę to zrobić ręcznie za pomocą wyszukiwania binarnego też, ale zastanawiałem się, czy istnieje już lib lub zbiór ten sposób.

Answer 1

Masz dwie opcje:

• java.util.Arrays.binarySearch na tablicach
  • (z różnych przeciążeń dla różnych typów tablicy)
• java.util.Collections.binarySearch na List
  • (z Comparable i Comparator przeciążenia).
  • Połącz z List.subList(int fromIndex, int toIndex) szukać części listy

Answer 2

Tylko dla kompletności, tutaj jest trochę funkcja Java, który włącza wyjście z Arrays.binarySearch w coś blisko do wyjścia z bisect_left. Najwyraźniej brakuje mi rzeczy, ale robi to za prostą sprawę.

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

Answer 3

Do tej daty (Java 8), to nadal brakuje, więc trzeba jeszcze stworzyć własną. Oto moje:

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

Testowane z (X oznacza klasę gdzie przechowywać metody statyczne, które zamierzam ponownie użyć):

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

Answer 4

Dlaczego nie zrobić szybki port sprawdzonyPython code samo? Na przykład, oto port Java dla 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; 
}