Java的等价于python中的二等分

Question

是否存在与python的等分库等价的java？使用python的等分线，您可以使用方向进行阵列平分。例如bisect.bisect_left作用：

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.

注：当然，当然，我现在我可以手动二进制搜索就此别过，但不知道是否已经有一个lib或集合这样做。

Answer 1

有两个选项：

• java.util.Arrays.binarySearch上阵列
  • （带有各种重载不同阵列的类型）
• java.util.Collections.binarySearch上List
  • （与Comparable和Comparator重载）。
  • 与List.subList(int fromIndex, int toIndex)结合在列表中搜索

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

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

Answer 4

为什么不做口岸快速久经考验Python code本身？例如，这里有一个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; 
}