Kapitel 3: Arrays
Ein Array speichert eine Folge von Werten, die alle den gleichen Datentyp besitzen. Die Technik, mit welcher wir Bezug auf die Werte eines Arrays nehmen, basiert darauf, dass die Werte in einem Array nummeriert sind. Das nennt man Indizierung. Das erste Element eines Arrays ist mit dem Index \(0\) assoziiert. Das letzte Element eines Arrays mit $n$ Elementen liegt an der Indexposition $n-1$. Hat ein Array den Bezeichner a, dann adressieren wir das $i$-te Element mit a[i], wobei i die Indexposition ist. Das so beschriebene Konstrukt ist ein eindimensionales Array. Arrays können aber auch mehrdimensional sein. Das ist dann der Fall, wenn die Elemente eines Arrays wiederum Arrays sind. Eine Matrix ist demzufolge ein Array von 1-dimensionalen Arrays, sodass sich insgesamt zwei Dimensionen ergeben. Weitere Dimensionen sind durch weitere Schachtelungen der Struktur möglich.
Arrays spielen bei vielen Aufgaben eine wichtige Rolle hinsichtlich der Datenmodellierung, nicht nur als reine Speicherstruktur. So stellen sie beispielsweise, was offensichtlich ist, die informationstechnischen Entsprechungen zu den Vektoren und Matrizen dar, die in der Wissenschaft und der wissenschaftlichen Programmierung häufig verwendet werden.
Arrays in Java
Um in einem Java-Programm ein Array anzulegen, sind drei Schritte erforderlich:
- Das Array ist mit seinem Namen und der Typangabe des zu speichernden Datentyps zu deklarieren.
- Das Array muss erzeugt werden.
- Die Array-Werte sind zu initialisieren.
Der folgende Codeschnipsel zeigt die drei Schritte anhand eines Arrays von int-Werten.
int[] a; // Array a vom Typ int
a = new int[N]; // Speicherplatz für N int-Werte reservieren
for (int i = 0; i < N; i++) // Initialisierung der einzelnen Werte in a
a[i] = 0;
Ein Array kann auch literal vereinbart werden, wenn wir die Werte dem Array direkt zuweisen. Deklaration, Speicherplatzreservierung und Wertzuweisung fallen dann zusammen. Wir sprechen dann auch von der Definition eines Arrays.
int[] a = {3, 42, 5, 10, 15, 1, 2}; // Definition von int-Array a
Das Speicherbild eines Arrays, können wir uns wie folgt visualisieren. Aus der soeben vorgestellten Array-Definition resultiert das folgende Speicherbild. Die Definition des Arrays a reserviert eine indizierte Speicherfläche mit den Werten des Arrays. a selbst ist eine Referenz, die auf den Beginn dieser Speicherfläche verweist.
Kommandozeilenargumente
Ein Array stellt uns Java zur Verfügung, ohne das wir selbst etwas dazu tun müssen. Es ist das Array args, ein String[]-Array als Parameter der main-Methode. Das Array repräsentiert die einem Java-Programm übergebenen Kommandozeilenargumente.
Wenn wir auf die Kommandozeilenargumente zugreifen können, die einem Programm bei dessen Aufruf zur Ausführung übergeben werden, erhalten wir, neben der interaktiven Eingabe, eine alternative Möglichkeit zur Dateneingabe. – Wir lesen die Kommandozeilenargumente aus. Damit eröffnet sich uns die Möglichkeit, Dateneingaben zu tätigen, ohne dass das Programm anhalten und auf die Eingabe warten muss. So können wir beispielsweise Programme implementieren, die unbeaufsichtigt, im Rahmen eines Batch-Betriebs ausgeführt werden.
1import de.pakad.udemy.StdOut;
2
3/**
4 * Ausgabe einer Begrüßung.
5 */
6public class Greeting {
7 /**
8 * Hauptprogramm. Ein Name wird als Kommandozeilenargument
9 * eingelesen und in einer Begrüßung wieder ausgegeben.
10 * <p>
11 * <strong>Achtung</strong>: Es ist zwingend ein
12 * Kommandozeilenargument erforderlich!
13 * @param args [0] - Name
14 */
15 public static void main(String[] args) {
16 // wir nutzen das Array args, welches die Kommandozeilenargumente,
17 // die beim Programmaufruf übergeben werden
18 String name = args[0]; // erstes Kommandozeilenargument
19 StdOut.printf("Hallo %s, wie geht es Dir?", name);
20 }
21}
Listing 3.1: Greeting.java
Achtung: Der Zugriff auf ein nicht existierendes Array-Element ist ein Fehler!
Weil es sich bei Kommandozeilenargumenten um Zeichenketten handelt, haben wir diese, wenn erforderlich, in den benötigten Zieldatentyp zu konvertieren. Zu jedem primitiven Datentypen existiert in Java ein korrespondierender Datentyp, seine sogenannte Wrapperklasse. Primitive Datentypen sind int, double, boolean, char usw. Dann sind die zugehörigen Wrapperklassen: Integer, Double, Boolean, Character usw. – Die Systematik ist intuitiv einsichtig. Alle Wrapperklassen offerieren eine parse*()-Methode, die ihrem jeweiligen Datentyp entspricht, wie parseInt() oder parseDouble().
Das Programm Newton.java zeigt anhand einer nützlichen Anwendung, wie Zeichenketten in numerische Werte konvertiert werden. Es wird die Quadratwurzel einer nicht negativen reellen Zahl berechnet. Diese wird als einziges Kommandozeilenargument erwartet. Das ist die Eingabe.
Den implementierten Algorithmus brauchen Sie, wenn Sie ihn nicht kennen, nicht lernen. Das Programm soll lediglich die Konvertierung String nach Zahl nutzen und demonstrieren, mit welch einfachen Mitteln komfortable und nutzbringende Programm geschrieben werden können.
Das Programm nutzt das sogenannte Heron-Verfahren, einen vereinfachten Spezialfall des Newton-Verfahrens. Das ist ein iteratives Näherungsverfahren zur Bestimmung der Quadratwurzel einer Zahl $c$. In jedem Iterationsschritt wird die Wurzel weiter angenähert. Ausgehend von einem groben Schätzer, der eingegebenen Zahl selbst, wird durch einfache Mittelwertbildung die Wurzel angenähert. Achtung: c darf nicht $\leq 0$ sein!
1import de.pakad.udemy.StdOut;
2
3/**
4 * Berechnung der Quadratwurzel einer positiven reellen Zahl
5 * von Type {@code double}.
6 */
7public class Newton {
8 /**
9 * Hauptprogramm. Ein {@code double}-Wert wird als Argument
10 * der Kommandozeile eingelesen und dessen Quadratwurzel
11 * ausgegeben.
12 * <p>
13 * Heron-Verfahren:
14 * \[
15 * x_{n+1} = \frac{1}{2} \left(x_n + \frac{c}{x_n}\right)
16 * \]
17 *
18 * <strong>Achtung</strong>: Eingaben ≤ 0 führen in der aktuellen
19 * Implementierung zu eine Endlosschleife bzw. Division durch Null.
20 * Diese Fälle werden im Code <strong>nicht</strong> abgefangen!
21 *
22 * @param args [0] - Radikand (<b>positive</b> reelle Zahl)
23 */
24 public static void main(String[] args) {
25 double c = Double.parseDouble(args[0]);
26
27 double epsilon = 1.e-15; // hinreichende Genauigkeit
28 double t = c; // Schätzer
29
30 while(Math.abs(t - c/t) > epsilon) // solange nicht genau genug ...
31 t = (t + c/t) / 2.0; // neuer Mittelwert
32
33 StdOut.println(t);
34 }
35}
Listing 3.2: Newton.java
Erläuterung für mathematisch Interessierte:
Ziel: Berechnung von \(\sqrt{c}\)
Funktion: Es wird \(f(x) = x^2 - c\) verwendet.
Nullstelle: Die gesuchte Wurzel ist die positive Nullstelle, für die \(f(x) = 0\) gilt.
Newton-Formel: Die allgemeine Formel
\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]wird mit \(f'(x) = 2x\) zu:
\[x_{n+1} = x_n -\frac{x_n^2-c}{2x_n}\]Vereinfachte Iterationsformel: (Heron-Verfahren):
\[x_{n+1} = \frac{1}{2}\left(x_n + \frac{c}{x_n}\right)\]Diese Formel wurde in Newton.java verwendet.
Arrays als Werkzeuge der Datenmodellierung
Skalarprodukt von zwei Vektoren
Als ein erstes Beispiel wollen wir zwei Vektoren implementieren und deren Skalarprodukt berechnen. Das ist die Summe der paarweisen Produkte ihrer Elemente.
1import de.pakad.udemy.StdOut;
2
3/**
4 * {@code ScalarProduct} modelliert zwei Vektoren, deren
5 * Skalarprodukt berechnet und ausgegeben wird.
6 */
7public class ScalarProduct {
8 /**
9 * Hauptprogramm. Die zu multiplizierenden Vektoren
10 * sind fix codiert.
11 *
12 * @param args nicht genutzt
13 */
14 public static void main(String[] args) {
15 double[] v1 = {1.2, 2.8, 3.0, 4.0}; // erster Vektor
16 double[] v2 = {3.0, 4.2, 3.1, 5.5}; // zweiter Vektor
17 double prod = 0.0; // skalare Vektorprodukt
18
19 // elementweises summieren der Produkte
20 for (int i=0; i<v1.length; i++)
21 prod = v1[i] * v2[i];
22
23 StdOut.println(prod);
24 }
25}
Listing 3.3: ScalarProduct.java
Jedes Array besitzt ein Attribut namens length, welches die Anzahl seiner Elemente enthält.
Die for-Schleife iteriert über die Vektoren unter Nutzung der jeweiligen Indizes, die mit $0$ beginnen und bei v1.length - 1 enden.
Da v1 und v2 jeweils gleich viele Elemente haben müssen, um ein Skalarprodukt zu berechnen, ist es unerheblich, ob wir die Anzahl der Elemente bei v1 oder v2 erfragen.
Lottozahlen
Betrachten wir ein zweites Beispiel. Lotto.java simuliert das zufällige „Ziehen ohne Zurücklegen", wie wir es von der Ziehung der Lottozahlen kennen.
Ziehen ohne Zurücklegen bedeutet: eine bereits gezogene Zahl kann kein weiteres Mal gezogen werden.
Wir haben ein Array mit N ganzen Zahlen. Davon sollen M zufällig gezogen werden. Jeweils direkt die Zahlen über einen zufällig generierten Index adressieren/ziehen zu wollen ist keine gute Idee, kann doch die eine oder andere Zufallszahl mehrfach vorkommen. Die Idee ist es daher, die ersten M Positionen im Array mit den Werten zufällig gezogener Werte auszutauschen. Sollten dabei Doppelungen der zufällig generierten Zahlen vorkommen, so stört das nicht. Wir greifen uns als Ergebnis einfach die ersten M Zahlen im Array. Im konkreten Fall ist M gleich \(6\) und N ist \(49\).
1import de.pakad.udemy.StdOut;
2
3/**
4 * Simulation der Lottozahlenziehung 6 aus 49 (Ziehen ohne Zurücklegen).
5 */
6public class Lotto {
7 /**
8 * Hauptprogramm.
9 *
10 * @param args nicht genutzt
11 */
12 public static void main(String[] args) {
13 int N = 49, M = 6; // M aus N
14
15 // Initialisierung
16 int[] numbers = new int[N];
17 for (int i=0; i<N; i++)
18 numbers[i] = i+1;
19
20 // Ziehung der Lottozahlen
21 for (int i=0; i<M; i++) {
22 // Idee: tausche numbers[i] mit einem zufälligen
23 // Wert zu dessen Rechten
24 int r = i + (int)(Math.random() * (N-i)); // Zufallsindex rechts von i
25 int tmp = numbers[i];
26 numbers[i] = numbers[r];
27 numbers[r] = tmp;
28 }
29
30 // Ergebnisausgabe
31 for (int i=0; i<M; i++)
32 StdOut.print(numbers[i] + " ");
33 StdOut.println();
34 }
35}
Listing 3.4: Lotto.java
In Zeile 23 ist es erforderlich, die generierte Zufallszahl, eine Gleitkommazahl, in eine ganze Zahl umzurechnen.
(Math.random() * (N - i))erzeugt eine Zufallszahl im Intervall \([0, N-i)\). Das ist ist eine Gleitkommazahl, mit einem Maximum kleiner alsN.(int)schneidet die Nachkommastellen ab, sodass wir im Ergebnis, nach Addition voni, ganze Zahlen im Intervall $[0, N-1]$ erhalten.
Matrizenmultiplikation
Mehrdimensionale Arrays entstehen in Java dadurch, dass die Elemente eines Arrays wiederum Arrays sind. Theoretisch kann man so mehrdimensionale Strukturen mit beliebiger Tiefe aufbauen. In der Praxis finden wir viele 2-dimensionale Arrays (Matrizen), einige 3-dimensionale Arrays (Würfel) und selten Arrays mit mehr Dimensionen.
Wir wollen uns als Beispiel die Multiplikation zweier quadratischer Matrizen ansehen. Die sind, damit wir uns auf das Wesentliche konzentrieren können, im Programm fest vorgegeben. Im Vordergrund steht die Behandlung mehrdimensionaler Arrays.
Die Elemente der Ergebnismatrix berechnen sich bei der Multiplikation zweier \(n \times n\)-Matrizen gemäß der folgenden Formel:
\[c_{ij} = \sum_{j=0}^{n-1}{a_{ij}\cdot b_{jk}} \forall i = 0, \dots, n-1 \land k = 0, \dots, n-1\]
Jedes c[i][j] im Produkt von a[] und b[] wird dadurch berechnet, dass das Skalarprodukt der Zeile i von a[] mit der Spalte j von b[] ermittelt wird (vgl. Listing 3.3).
1import de.pakad.udemy.StdOut;
2
3/**
4 * {@code MatrixMult} modelliert zwei <i>n</i>x<i>n</i>-Matrizen,
5 * die miteinander multipliziert werden.
6 */
7public class MatrixMult {
8 /**
9 * Hauptprogramm. Die zu multiplizierenden Matrizen sind
10 * fix codiert.
11 *
12 * @param args nicht genutzt
13 */
14 public static void main(String[] args) {
15 int[][] a = {{ 1, 2, 3, 4},
16 { 5, 6, 7, 8},
17 { 9, 10, 11, 12},
18 {13, 14, 15, 16}};
19 int[][] b = {{17, 18, 19, 20},
20 {21, 22, 23, 24},
21 {25, 26, 27, 28},
22 {29, 30, 31, 32}};
23 int n = a.length; // Dimension
24 int[][] c = new int[n][n]; // Speicher für Ergebnismatrix
25
26 // Matrixmultiplikation
27 for (int i=0; i<n; i++) {
28 for (int j=0; j<n; j++) {
29 c[i][j] = 0;
30 for (int k=0; k<n; k++)
31 c[i][j] += a[i][k] * b[k][j];
32
33 }
34 }
35
36 // Ergebnisausgabe
37 for (int i=0; i<n; i++) {
38 for (int j=0; j<n; j++)
39 StdOut.printf("%6d", c[i][j]);
40 StdOut.println();
41 }
42 }
43}
Listing 3.5: MatrixMult.java
Zeichenkettenvergleich
Der Datentyp String ist in Java eine Klasse zur Speicherung von Zeichenketten. Intern werden diese als char[] (Array von Zeichen) abgebildet. Die Klasse String erlaubt es, Zeichenketten mit den üblichen Vergleichsoperatoren auf Gleichheit, größer, kleiner usw. zu untersuchen. Je zwei Zeichenketten werden dabei zeichenweise miteinander verglichen. Aus der Besprechung des Datentyps char wissen Sie um dessen Codierung. Das Zeichen 'B' ist größer als das Zeichen 'A', weil sein numerischer Code, die $66$, größer als der von 'A', $65$, ist.
Das Programm StrCompare.java simuliert einen Zeichenkettenvergleich, wie String ihn durchgeführt. Analog zu String nutzen wir zur Modellierung der zu vergleichenden Zeichenketten je ein Array von Zeichen. readlnChars() aus de.pakad.udemy.StdIn liest eine Zeichenkette ein und liefert sie uns als ein Array von Zeichen zurück.
1import de.pakad.udemy.StdIn;
2import de.pakad.udemy.StdOut;
3
4/**
5 * Vergleich zweier Zeichenketten.
6 */
7public class StrCompare {
8 /**
9 * Hauptprogramm. Zwei Zeichenketten werden interaktiv in
10 * Form von {@code char}-Arrays eingelesen und miteinander
11 * lexikographisch verglichen.
12 *
13 * @param args nicht genutzt
14 */
15 public static void main(String[] args) {
16 char[] s1 = StdIn.readlnChars("1. Zeichenkette: ");
17 char[] s2 = StdIn.readlnChars("2. Zeichenkette: ");
18
19 StdOut.print(s1);
20
21 // Zeichenketten zeichenweise vergleichen
22 int i; // Index, bis zu dem verglichen wurde
23 for (i=0;
24 i<s1.length && // solange s1 noch Zeichen hat
25 i<s2.length && // und s2 noch Zeichen hat
26 s1[i]==s2[i]; // und die Zeichen gleich sind
27 i++)
28 ; // Schleifenrumpf ist leer
29
30 // prüfe, warum for-Schleife beendet wurde
31 if (i==s1.length && i==s2.length)
32 StdOut.print(" = "); // beide vollständig verglichen
33 else if (i==s1.length)
34 StdOut.print(" < "); // s1 kürzer als s2
35 else if (i==s2.length)
36 StdOut.print(" > "); // s2 kürzer als s1
37 else if (s1[i]<s2[i])
38 StdOut.print(" < "); // s1 kleiner als s2
39 else
40 StdOut.print(" > "); // s2 größer als s1
41
42 StdOut.println(s2);
43
44 }
45}
Listing 3.6: StrCompare.java
Sieb des Eratosthenes
In diesem Beispiel geht es darum, Primzahlen zu identifizieren. Mithilfe des Indexes eines Arrays modellieren wir die zu analysierenden Zahlen. Die einzelnen Array-Elemente sind Wahrheitswerte. Sie zeigen an, ob der jeweilige Index-Wert eine Primzahl ist oder nicht.
Das hier gezeigte Verfahren geht auf den griechischen Mathematiker Eratosthenes zurück. Die Idee hinter dem Verfahren ist einfach.
- Wir gehen von der „kühnen Annahme" aus, alle Zahlen seien Primzahlen. D. .h., wir initialisieren ein boolesches Array für alle seine Elemente mit
true. - Wir beginnen bei der kleinsten bekannten Primzahl. Sie wird durch den Index-Wert $2$ repräsentiert.
- Von der aktuellen Zahl (Index-Wert) ausgehend, streichen wir alle Vielfachen dieser Zahl. Das sind keine Primzahlen. Wir setzen die entsprechenden Array-Elemente auf
false. - Wir wiederholen Schritt 3 mit dem nächsten Index, wenn dieser nicht bereits mit
falsemarkiert ist.
Das ist ein typischer „2-Zeigefinger-Algorithmus". Der linke Zeigefinger geht elementweise durch das Array, während der rechte Zeigefinger die Vielfachen markiert.
1import de.pakad.udemy.StdOut;
2
3/**
4 * Sieb des <i>Eratosthenes</i>.
5 */
6public class Eratosthenes {
7 /**
8 * Hauptprogramm. Es wird eine positive Ganzzahl, größer
9 * oder gleich 2 eingelesen, bis zu welcher Zahlen auf
10 * ihre Primeigenschaft untersucht werden.
11 *
12 * @param args [0] natürliche Zahl, bis zu der analysiert wird
13 */
14 public static void main(String[] args) {
15 /*
16 * Idee: - Nimm ein boolesches Array mit den Indizes als zu
17 * untersuchende Werte.
18 * - Markiere alle Elemente mit true (alle Zahlen sind prim).
19 * - Gehe das Array, bei 2 beginnend, durch und markiere
20 * alle Vielfachen mit false (nicht prim).
21 * - alle bereits mit false gekennzeichneten Elemente
22 * können übersprungen werden.
23 */
24 boolean[] prime; // zu analysierende Zahlen
25 int i, j; // Laufvariablen, linker und rechter Zeigefinger
26 int N = Integer.parseInt(args[0]); // bis zu Zahl N analysieren
27
28 prime = new boolean[N+1]; // Speicherplatz für Array
29 for (i=2; i<N+1; i++)
30 prime[i] = true; // kühne Annahme: alle Zahlen sind Primzahlen
31
32 // 2-Finger-Algorithmus
33 for (i=2; i<N+1; i++) // linker Zeigefinger -> Zahlen (i) durchlaufen
34 if (prime[i]) {
35 StdOut.print(i + " "); // Primzahl gefunden -> ausgeben
36 for (j=i*i; j<N+1; j+=i) // rechter Zeigefinger -> Vielfache von i
37 prime[j] = false; // streichen
38 }
39
40 StdOut.println();
41 }
42}
Listing 3.7: Eratosthenes.java
Hinweis: Man mag geneigt sein, j in Zeile 33 mit i+i zu initialisieren. Wir verwenden i*i, weil alle kleineren Vielfachen von i bereits gestrichen sind. i*i spart also unnötige Berechnungsschritte.
Josephus-Problem
Der Name „Josephus-Problem" geht auf eine Geschichte des Flavius Josephus zurück. Der soll sich um 67 n. Chr., beim Kampf um die Stadt Jotapata, mit 40 Männern in einer Höhle vor den Römern versteckt haben. Um nicht von den Römern gefangengenommen zu werden, beschlossen die insgesamt 41 Männer, kollektiven Selbstmord zu begehen. Sie stellten sich im Kreis auf. Jeder dritte Mann, sollte reihum von seinem rechten Nebenmann enthauptet werden. Josephus stellte sich an die Position 16. er blieb als vorletzter Mann übrig, einigte sich mit dem ebenfalls noch lebenden Kameraden und beide ergaben sich den Römern.
Wir können ein Array verwenden, um die Kreisaufstellung der Männer zu modellieren. Der Index eines Elements repräsentiert den jeweiligen Mann. Der Wert an der Stelle i des Arrays ist ein Verweis auf den folgenden Mann in der Kreisaufstellung. Mit jedem Mann der ausscheidet, ist der Verweis entsprechend auf den nächsten noch lebenden Nachbarn zu setzen.
Hinweis: Weil ein Array mit Null beginnend indiziert ist, hätte Josephus in unserer Modellierung die Position i gleich 15.
Das Programm Josephus.java verallgemeinert das Problem dahingehend, die Anzahl der Männer und das Abzählen, der jeweils wievielte Mann sein Leben verliert, flexibel zu gestalten. Die notwendigen Parameter werden als Kommandozeilenargumente an das Programm übergeben. Das entspricht einem typischen Abzählreim, den Kinder spielen. N Kinder stellen sich im Kreis auf. Der Abzählreim hat k Silben. Beim Abzählen scheidet jedes k-te Kind aus.
1import de.pakad.udemy.StdOut;
2
3/**
4 * Implementierung eines Abzählreims.
5 */
6public class Josephus {
7 /**
8 * Hauptprogramm. Die Anzahl der Kinder sowie die Anzahl der Silben
9 * des Abzählreims werden als Kommandozeilenargument übergeben.
10 *
11 * @param args <br>[0] - Anzahl der Kinder<br>
12 * [1] - Anzahl der Silben
13 */
14 public static void main(String[] args) {
15 int[] children; // Kinder
16 int i, index; // Laufvariablen
17 int N = Integer.parseInt(args[0]); // Anzahl Kinder
18 int k = Integer.parseInt(args[1]); // Anzahl der Silben
19
20 children = new int[N]; // Array der Kinder
21 for (i=0; i<N; i++) // Kinder im Kreis aufstellen
22 children[i] = (i+1) % N; // Verweis auf das nächste Kind
23
24 index = N-1; // letztes Kind
25 while (children[index] != index) { // solange Kind nicht auf sich selbst verweist ...
26 for (i=1; i<k; i++) // abzählen
27 index = children[index]; // von einem Kind zum nächsten im Kreis
28
29 // wir stehen jetzt vor dem ausscheidenden Kind
30 StdOut.printf("ausgeschieden: %2d\n", children[index]);
31 // ausgeschiedenes Kind aus dem Kreis ausschließen
32 children[index] = children[children[index]];
33 }
34 StdOut.printf("Und der Gewinner ist: %2d", index);
35 }
36}
Listing 3.8: Josephus.java
Die Formulierung next[i] = (i + 1) % N, Zeile 24, sorgt dafür, dass initial jedes Kind auf seinen direkten Nachfolger verweist. Das letzte Kind im Array verweist auf das Kind an Index-Position 0, sodass der Kreis geschlossen wird.
Lineare und binäre Suche
Wir betrachten im Folgenden Arrays ganzer Zahlen.
Lineare Minimum-Suche
Wir suchen das Minimum in einem unsortierten Array ganzer Zahlen. Wir lesen die zu durchsuchenden Zahlen mithilfe der Methode readlnInts() aus de.pakad.udemy.StdIn ein, die uns ein entsprechendes Array zurückgibt.
|
|
Listing 3.9: MinSearch.java
Bei einem aufsteigend sortierten Array erübrigt sich die Suche des Minimums. Es steht an Index-Position 0. Wir könnten es direkt auslesen. In diesem Fall wäre die Laufzeit zum Finden des Minimums konstant. Wir benötigten nur einen Schritt, bräuchten keine Schleife zu implementieren.
Anders verhält es sich, wenn ein Array unsortiert ist. Wir haben das gesamte Array zu durchlaufen. Ohne jeden Wert des Arrays gesehen zu haben, können wir nicht sicher sein, das Minimum gefunden zu haben. Wir beginnen mit dem ersten Wert des Arrays als vorläufigem Minimum. Hat das Array insgesamt $n$ Elemente, haben wir $n-1$ Vergleiche durchzuführen, um das Minimum sicher zu bestimmen.
Selbst wenn wir eine sortierte Folge ganzer Zahlen in das Programm eingeben, profitiert die lineare Minimum-Suche nicht davon. Sie trifft keinerlei Annahmen über eine gegebenenfalls vorhandene Ordnung.
$ java MinSearch
Folge ganzer Zahlen: 1 2 8 -10 23 44 42 23
Minimum -10 an Position 3
$ java MinSearch
Folge ganzer Zahlen: 1 2 3 4 5 6 7 8 9 10
Minimum 1 an Position 0
$ _
Lineare Suche
Etwas anders sieht der Sachverhalt aus, wenn wir die Aufgabenstellung modifizieren. Wir suchen jetzt nach dem ersten Vorkommen eines bestimmten Wertes. Wir gehen von einem unsortierten Array aus.
1import de.pakad.udemy.StdIn;
2import de.pakad.udemy.StdOut;
3
4/**
5 * Lineare Suche in einem {@code int}-Array.
6 */
7public class LinSearch {
8 /**
9 * Hauptprogramm. Das zu durchsuchende Array sowie der
10 * zu suchende Wert werden interaktiv eingegeben.
11 *
12 * @param args nicht genutzt
13 */
14 public static void main(String[] args) {
15 int[] a = StdIn.readlnInts("Bitte eine Folge ganzer Zahlen: ");
16 int x = StdIn.readlnInt("Zu suchende Zahl..............: ");
17
18 int i; // Laufvariable
19 for (i=0; i<a.length && a[i]!=x; i++) ; // suchen
20
21 if (i == a.length) StdOut.println("Nicht gefunden");
22 else StdOut.println("Gefunden an Position " + i);
23 }
24}
Listing 3.10: LinSearch.java
Im günstigsten Fall ist das erste verglichene Element ein Treffer. Im ungünstigsten Fall sind $n$ Vergleiche erforderlich, bis das gesuchte Element gefunden wird oder die Aussage getroffen werden kann, es im Array nicht gefunden zu haben.
Binäre Suche
Die binäre Suche setzt ein geordnetes Array voraus. Die Art der Ordnung muss bekannt sein. Ich gehe hier von einem aufsteigend geordnetem Array aus.
1import de.pakad.udemy.StdIn;
2import de.pakad.udemy.StdOut;
3
4/**
5 * Binäre Suche in einem aufsteigend geordneten {@code int}-Array.
6 */
7public class BinSearch {
8 /**
9 * Hauptprogramm. Das zu durchsuchende Array sowie der
10 * zu suchende Wert werden interaktiv eingegeben.
11 *
12 * @param args nicht genutzt
13 */
14 public static void main(String[] args) {
15 int[] a = StdIn.readlnInts("Aufsteigend geordnete Folge ganzer Zahlen: ");
16 int x = StdIn.readlnInt("Zu suchende Zahl.........................: ");
17
18 /*
19 * Suchstrategie:
20 * 1. wir beginnen in der Mitte (des verbleibenden Arrays)
21 * 2. wenn Wert nicht gefunden:
22 * -- wenn gesuchter Wert größer, dann rechts weitersuchen mit 1
23 * -- ansonsten links weitermachen mit 1
24 */
25 int lft = 0, rgt = a.length-1, mid = (lft+rgt)/2; // Suchindizes
26
27 // durchsuchen, solange noch Chance besteht ...
28 while (lft<=rgt && a[mid]!=x) {
29 if (a[mid]<x) lft = mid+1; // neue linke Grenze
30 else rgt = mid-1; // neue rechte Grenze
31 mid = (lft+rgt)/2; // neue Mitte
32 }
33
34 // wenn linker Index > als rechter Index, dann Suche erfolglos
35 if (lft > rgt) StdOut.println("Nicht gefunden");
36 else StdOut.println("Gefunden an Position " + mid);
37 }
38}
Listing 3.11: BinSearch.java
Die binäre Suche nutzt die bekannte Ordnung des Arrays, die Voraussetzung ist, aus. Wie bei der Suche in einem Telefonbuch, wird die Suche in der Mitte begonnen. Wird das Element gefunden, ist die Suche beendet. Ist das gesuchte Element jedoch größer als der Wert des mittleren Elements, wird die Suche auf der rechten Seite fortgesetzt, andernfalls auf der linken Seite. Hier wird jeweils nach dem gleichen Prinzip verfahren. Das verbleibende Array wird, von dessen Mitte ausgehend, weiter durchsucht.
Die erläuterte Suchstrategie halbiert mit jedem Schritt die Problemgröße, die Anzahl der der zu durchsuchenden Elemente. Sei diese Anzahl \(n\). Dann sind, bei steter Halbierung, maximal \(\log_2(n)\) Vergleiche erforderlich, um einen gesuchten Wert zu finden oder aussagen zu können, ihn im Array nicht finden zu können.
Beispiel: In einem Array mit 1 Million Einträgen sind maximal \(\log_2(1,000,000) \approx 20\) Vergleiche erforderlich. Bei der linearen Suche sind das, ob man Glück hat oder nicht, $1$ bis \(1,000,000\) Vergleiche. Im statistischen Mittel ergeben sich \(500,000\) Vergleiche. – Die binäre Suche ist der linearen Suche also deutlich überlegen.
Tatsächlichen kann man zeigen, dass es mittels Vergleichen nicht möglich ist, schneller zu suchen, als es die binäre Suche tut.
$ java BinSearch
Sortierte Folge ganzer Zahlen: 1 2 3 4 5 6 7 8 9 10 42 78 99
Zu suchende Zahl.............: 10
Gefunden an Position 9
$ _