Java tương đương với bisect trong python

Question

Có java tương đương với thư viện bisect của python không? Với băn khoăn của python bạn có thể làm mảng bisection với hướng dẫn. Ví dụ bisect.bisect_left làm:

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.

Lưu ý: Chắc chắn tất nhiên tôi bây giờ tôi có thể làm điều này bằng tay với một tìm kiếm nhị phân quá, nhưng tự hỏi nếu đã có một bộ sưu tập lib hoặc làm điều này.

Answer 1

Bạn có hai lựa chọn:

• java.util.Arrays.binarySearch trên mảng
  • (với quá tải khác nhau với nhiều loại mảng khác nhau)
• java.util.Collections.binarySearch trên List
  • (với Comparable và Comparator quá tải).
  • Kết hợp với List.subList(int fromIndex, int toIndex) để tìm kiếm phần của một danh sách

Answer 2

Chỉ cần cho đầy đủ, đây là một chức năng java nhỏ mà quay đầu ra từ Arrays.binarySearch vào một cái gì đó gần với sản lượng từ bisect_left. Tôi rõ ràng là thiếu những thứ, nhưng điều này làm công việc cho trường hợp đơn giản.

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

Đến ngày này (Java 8), điều này vẫn bị thiếu, vì vậy bạn vẫn phải tự tạo. Dưới đây là tôi:

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

Thử nghiệm với (X là một lớp học, nơi tôi lưu trữ các phương pháp tĩnh mà tôi có ý định tái sử dụng):

@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

Tại sao không làm một cổng nhanh chóng của các thử và thử nghiệmPython code chinh no? Ví dụ: đây là cổng Java cho 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; 
}