TuH2 java

Wiki-Quelltext dieser Seite.

<language>Java</language>
Zurück zur Hauptseite [[Teile und Herrsche 2]]



<language>Java</language>
==Java - Variante zu Teile und Herrsche 2==

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

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



</code>

Die Binäre Suche kann auch Iterativ definiert werden. Es werden 3 INT-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 Endeindex 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 aus die Schleife verlassen wurde. Im Fall, dass ''Start'' größer als ''Ende'' ist, 


Betrachten wir nun die ''iterative Variante'' der ''binären Suche'':
<code>
// 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;
		
	}
</code>
<eval>
System.out.print(5);

//binSuch(myArray, 4);
</eval>

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

<math>
\begin{array}{lcl}
\text{Start} & = & 0 \\
\text{Ende} & = & Feldleange - 1 \\
\text{Feldleange zu Begin} & = & \text{start} + \text{Ende} \\
\text{Mitte des Feldes} & = & \dfrac{\text{Start} + \text{Ende}}{2} \\
\end{array}
</math>

Das Intervall ändert sich wie folgt:

<math>
\begin{array}{lcl}
\text{Neue Feldlaenge} & = &  \text{Ende} - \text{Start} + 1 \\
 & = & \text{Ende} - (\text{Mitte} + 1) + 1 \\
 & = & \text{Ende} - \text{Mitte des Feldes} \\
 & = & \text{Ende} - \dfrac{\text{Start} + \text{Ende}}{2} \\
 & = & \dfrac{2 \cdot \text{Ende}}{2} - \dfrac{\text{Start} + \text{Ende}}{2} \\
 & = & \dfrac{\text{Ende} - \text{Start}}{2}
\end{array}
</math>

Kurz gefasst ändert sich das Intervall in jedem Durchlauf der Schleife von der Länge ''n'' auf <math>\dfrac{n - 1}{2}</math>. 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 <math>2^k</math> Operationen um ''n'' Elemente zu durchsuchen.

<math>2^k = n</math> Das lässt sich mit dem Logarithmus zur Basis 2 errechnen.

 <math>\log_{2} n = k \curvearrowright \mathcal{O}(\log_2 n)</math> 
 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 [[http://www.michael-hielscher.de/wiki/index.php/Aufgaben_-_TuH2#Aufgaben_zur_Bin.C3.A4ren_Suche]].
Für den direkten Vergleich haben wir hier die notwendige Funktion für die ''sequenzielle Suche'' zu Verfügung gestellt.
<code>	
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;
		
	}
</code>

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!
<code>
//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);
	}

</code>

<eval>
System.out.print(binSuchRek(myArray, 20321, 0, myArray.length));
</eval>

==Karatsuba in Java==

Dies ist eine Mögliche Implementierung in Java:
<!--
<code>
BigInteger karatsuba (BigInteger x, BigInteger y)
	{
		int n = Math.max(x.bitLength(),y.bitLength());
		if (n <= 1) return x.multiply(y);
		
		n=n /2;
		BigInteger xH = x.shiftRight(n);
		BigInteger xL = x.subtract (xH.shiftLeft(n));
		BigInteger yH = y.shiftRight (n);
		BigInteger yL = y.subtract (yH.shiftLeft(n));
		
		BigInteger p1 = karatsuba(xH, yH);
		BigInteger p2 = karatsuba(xL, yL);
		BigInteger p3 = karatsuba (xL.add(xH), yL.add(yH));
		
		return p1.shiftLeft(2*n).add(p3.subtract (p1).subtract (p2).shiftLeft(n)).add(p2);
	}
}
</code>
<eval>

</eval>

-->