Binary Suche in einer geordneten Liste in java

Question

Ich suche nach einer Möglichkeit, einen Code in Java zu implementieren, die die gleiche Art und Weise wie eine binäre Suche in einer geordneten Arraylist, aber für eine geordnete Liste Dank

Answer 1

Der Algorithmus arbeitet sollte das gleiche für eine ArrayList und eine List, vorausgesetzt sie sind beide bestellt.

Answer 2

Sie sollten auch daran denken, dass Sie keine Binärsuche durchführen können, wenn die Liste nicht geordnet ist. Es macht keinen Sinn. Binäre Suche ist O(log n), weil Sie an jeder Stelle die Hälfte der Liste ignorieren können, da Sie wissen, dass es geordnet ist. Wenn die Liste nicht geordnet ist, ist Ihre Suche O (n) und Sie können keine Binärdatei verwenden.

Ihre eigene Implementierung für binäre Suche sollte wie folgt aussehen:

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // test if array is empty 
    if (imax < imin) 
    // set is empty, so return value showing not found 
    return KEY_NOT_FOUND; 
    else 
    { 
     // calculate midpoint to cut set in half 
     int imid = midpoint(imin, imax); 

     // three-way comparison 
     if (A[imid] > key) 
     // key is in lower subset 
     return binary_search(A, key, imin, imid-1); 
     else if (A[imid] < key) 
     // key is in upper subset 
     return binary_search(A, key, imid+1, imax); 
     else 
     // key has been found 
     return imid; 
    } 
} 

Quelle: Wikipedia

Wenn Sie möchten, dann java.util Implementierung verwenden verwenden:

java.util.Arrays.binarySearch(int[] a, int key) 

Array a sollte natürlich sortiert werden.

Answer 3

"Binäre Suche" macht nur Sinn, wenn die Elemente der Liste (oder irgendeine Art von Zeigern auf die Elemente) sequenziell im Speicher organisiert sind, so dass, wenn Sie wissen, dass Ihre Suche auf die Indizes Low und High eingeschränkt wurde. Sie können direkt zu dem Element springen (Low + High)/2, ohne alle anderen Elemente durchgehen zu müssen. Dies wird für eine allgemeine Liste nicht funktionieren, die eine LinkedList sein könnte. Für so etwas kann man nicht wirklich besser sein, als am Anfang der Liste zu beginnen und alle Elemente der Reihe nach durchzugehen.

Answer 4

können Sie

Collections.<T>binarySearch(List<T> list, T key)

für binäre Suche auf jedem List verwenden. Es funktioniert auf ArrayList und auf LinkedList und auf jedem anderen List.

jedoch:

binäre Suche ist schnell nur, wenn Sie den direkten Zugriff auf jedes Element haben:

Dieses Verfahren läuft in log (n) Zeit für einen "random access" Liste (die in der Nähe bietet -konstanzal positionsabhängiger Zugriff). Wenn die angegebene Liste die RandomAccess-Schnittstelle nicht implementiert und groß ist, führt diese Methode eine iteratorbasierte binäre Suche durch, die O (n) -Transaktionen und O (log n) -Elementvergleiche durchführt.

Wenn Ihr List bietet keine „random access“ Sie mehr Glück, indem Sie eine Kopie dieser List haben könnten, das dies tut liefern.

LinkedList<String> list = new LinkedList<String>(); 
// fill 

Entweder wie so

ArrayList<String> fastList = new ArrayList<String>(list); 
Collections.binarySearch(fastList, "Hello World"); 

oder vielleicht wie so

String[] array = list.toArray(new String[list.size()]); 
Arrays.binarySearch(array, "Hello World"); 

Wenn Ihr List ist standardmäßig nicht bestellt und haben Sie es zu sortieren, bevor suchen Sie vielleicht das beste bekommen Ergebnis, indem Sie es mit Arrays seit

Collections.sort(list); 

tun 0

erstellt ein temporäres Array, das sortiert und zum Erstellen der Liste verwendet wird, die Sie verhindern können, wenn Sie dies direkt mit Arrays tun.

String[] array = list.toArray(new String[list.size()]); 
Arrays.sort(array); 
Arrays.binarySearch(array, "Hello World");