equivalente de Java a bisección en python

Question

¿Hay un equivalente de java para la biblioteca de bisectos de python? Con la bisectriz de pitón puedes hacer una bisección de array con direcciones. Por ejemplo bisect.bisect_left hace:

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.

Nota: Claro, por supuesto, que ahora puede hacerlo de forma manual con una búsqueda binaria también, pero se preguntó si ya existe una librería o una colección de hacer esto.

Answer 1

tiene dos opciones:

• java.util.Arrays.binarySearch en matrices
  • (con varias sobrecargas para diferentes tipos de matriz)
• java.util.Collections.binarySearch en List
  • (con Comparable y Comparator sobrecargas).
  • combinan con List.subList(int fromIndex, int toIndex) a buscar parte de una lista

Answer 2

simplemente para la corrección, he aquí una pequeña función de Java que convierte la salida de Arrays.binarySearch en algo cerca de la salida de bisect_left. Obviamente me faltan cosas, pero esto hace el trabajo para el caso simple.

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

Para esta fecha (Java 8), esto no es una forma, por lo que aún debe tomar su propia. Esta es la mía:

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

Probado con (siendo X la clase donde almaceno métodos estáticos que tengo la intención de volver a utilizar):

@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

Por qué no hacer un puerto rápido de la probadoPython code ¿sí mismo? Por ejemplo, aquí hay un puerto de Java para 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; 
}