Java ist gleichbedeutend mit Halbierung in Python

Question

Gibt es ein Java-Pendant zur Python-Bisect-Bibliothek? Mit der Python-Halbierung können Sie eine Array-Bisektion mit Richtungen durchführen. Zum Beispiel bisect.bisect_left tut:

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.

Hinweis: Sicher natürlich jetzt i i dies mit einer binären Suche auch manuell tun, aber fragte mich, ob es bereits eine lib oder Sammlung ist dies zu tun.

Answer 1

Sie haben zwei Möglichkeiten:

• java.util.Arrays.binarySearch auf Arrays
  • (mit verschiedenen Überlastungen für verschiedene Array-Typen)
• java.util.Collections.binarySearch auf List
  • (mit Comparable und Comparator Überladungen).
  • mit List.subList(int fromIndex, int toIndex) Kombinieren Teil einer Liste für Vollständigkeit

Answer 2

Nur zu suchen, ist hier eine wenig Java-Funktion, die die Ausgabe von Arrays.binarySearch in etwas nahe am Ausgang von bisect_left dreht. Ich vermisse offensichtlich Dinge, aber das macht den Job für den einfachen Fall.

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

Bis zu diesem Datum (Java 8) fehlt dieses noch, also müssen Sie noch Ihr eigenes machen. Hier ist meins:

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

Getestet mit (X ist die Klasse, wo ich statische Methoden speichern, die ich wieder zu verwenden beabsichtigen):

@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

Warum nicht einen schnellen Anschluss des tun bewährtenPython code selbst? Zum Beispiel, hier ist ein Java-Port für 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; 
}