TuH2 java

Aus ProgrammingWiki

Zurück zur Hauptseite Teile und Herrsche 2

Java - Variante zu Teile und Herrsche 2

Um mit den Java Beispielen experimentieren zu können findet ihr folgende vordefinierte Datenstrukturen und Hilfsmethoden:

int[] erzeugeFeld(int length) { int[] field = new int[length]; for (int i = 0; i < field.length; i++) { field[i] = i; } return field; } //Ein Array für Testzwecke int[] myArray = new int[] {0,2,4,6,8,10,12,14,16,18,20};

Die binäre Suche kann auch Iterativ definiert werden. Es werden 3 Integer-Variablen deklariert, welche als Zeiger auf das zu durchsuchende Array dienen. start beinhaltet den Index des ersten Elements, ende den Index des letzen Elements. mitte enthält jeweils den Index auf das in der Mitte Stehende Element. Die Schleife wird durchlaufen bis entweder der Ende-Zeiger größer oder gleich dem Start-Zeiger wird und das Gesuchte Element x nicht dem Element mit dem Index mitte entspricht. Die halbierung des Suchraums findet im Schleifenrumpf statt. Es wird überprüft ob das aktuell in der Mitte liegende Element kleiner als x ist. In diesem Fall wird der Startindex der Liste auf den Wert der Mitte plus 1 gesetzt. Andernfalls wird der Ende-Index auf den Wert der Mitte minus 1 gesetzt. In beiden Fällen wird jeweils der Suchraum damit entsprechend verkleinert. Im Anschluss wird die Mitte für die nächste Iteration berechnet.

Sobald das gesuchte Element gefunden wurde, sprich das gesuchte Element mit dem Element mit dem Index mitte übereinstimmt, wird die Schleife verlassen. Auch wenn der Start-Index nicht mehr kleiner ist als der Ende-Index wird die Schleife verlassen. Im Anschluss muss überprüft werden, warum die Schleife verlassen wurde. Wenn start nicht größer als ende ist, dann bedeutet dies, dass der Grund für das Verlassen der Schleife die Übereinstimmung von x mit dem Element mit dem Index mitte war. Nun muss also lediglich der entsprechende Index, nämlich die Variable mitte, zurückgegeben werden.

// Die eigentliche Such Methode, diese Liefert die Position an der das Element zu finden ist, // das Ergebnis -1 signalisiert das das Element nicht enthalten ist! int binSuch(int[] field, int x){ int start = 0; int ende = field.length-1; int mitte = (start + ende)/2; while(start <= ende && field[mitte] != x){ if(field[mitte] < x){ start = mitte + 1; }else ende = mitte - 1; mitte = (ende + start)/2; } if(start > ende){ return -1; }else return mitte; }

binSuch(myArray, 4);

ausführen

Um nun eine Aussage über die Effizienz treffen zu können, betrachten wir das Verhalten der Variablen, welche für die Positionen im zu durchsuchenden Feld verantwortlich sind.

Das Intervall ändert sich wie folgt:

Kurz gefasst ändert sich das Intervall in jedem Durchlauf der Schleife von der Länge n auf . Was heist das nun konkret? Wir haben 2 Intervalle zwischen denen es sich jeweils zu entscheiden gilt und dafür brauchen wir k durchläufe. Somit haben Operationen um n Elemente zu durchsuchen.

Das lässt sich mit dem Logarithmus zur Basis 2 errechnen.

 
Dieses Ergebnis zaubert ein grinsen ins Gesicht, 
da ein Algorithmus mit logarithmischer Laufzeit äußerst Effizient arbeitet.

Den Unterschied zwischen linearem und logarithmischen Aufwand kann man sich mittels empirischer Analyse vor Augen halten, dazu findet ihr zwei Aufgaben auf der Übungsseite [[1]]. Für den direkten Vergleich haben wir hier die notwendige Funktion für die sequenzielle Suche zu Verfügung gestellt.

int sequenzSuch(int[] field, int x){ int element= -1; for(int i = 0; i < field.length; i++){ if(field[i] == x) element = i; } return element; }

Für die Interessierten, hier findet ihr noch die rekursive Variante in Java. Im Wikipedia Artikel zur binären Suche ist ein kleiner Fehler, hier ist die korrigierte Variante!

//Rekursive Variante int binSuchRek(int [] field, int x, int start, int ende){ int mitte = start + ((ende - start)/ 2); if(mitte >= field.length || start > ende){ return -1; }else if(field[mitte] == x){ return mitte; }else if(field[mitte] < x ){ return binSuchRek(field, x, mitte + 1, ende); }else return binSuchRek(field, x, start, mitte - 1); }

System.out.print(binSuchRek(myArray, 20321, 0, myArray.length));

ausführen