Zum Hauptinhalt springen

Arrays

Autor:in

Karsten Brodmann

Veröffentlichungsdatum

19. September 2026

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:

  1. Das Array ist mit seinem Namen und der Typangabe des zu speichernden Datentyps zu deklarieren.
  2. Das Array muss erzeugt werden.
  3. 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.

Speicherbild eines Arrays
Abbildung 1

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 (String[]) 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.

Listing 1: Greeting.java
import StdLib.StdOut;

/**
 * Ausgabe einer Begrüßung.
 */
public class Greeting {
    /**
     * Es wird ein Name als Kommandozeilenargument eingelesen und
     * in Form einer Begrüßung wieder ausgegeben.
     * 
     * @param args [0] - Name
     */
    public static void main(String[] args) {
        String name = args[0];  // Kommandozeilenargument lesen
        StdOut.printf("Hallo %s, schön Dich zu sehen!\n", name);
    }
}

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!

Listing 2: Newton.java
import StdLib.StdOut;

/**
 * Berechnung reeller Wurzeln nach dem <em>Heron</em>-Verfahren.
 */
public class Newton {
    /**
     * Berechnung der positiven Wurzel einer positiven reellen Zahl.
     * 
     * @param args [0] - Radikand
     */
    public static void main(String[] args) {
        // Das 1. Kommandozeilenargument ist eine Gleitkommazahl.
        // Für diese soll die Quadratwurzel bestimmt werden.
        double c = Double.parseDouble(args[0]); 

        double epsilon = 1e-15;  // hinreichende Genauigkeit
        double t = c;            // Schätzer für die Quadratwurzel

        // solange Quadratwurzel nicht hinreichend genau bestimmt ...
        while (Math.abs(t - c/t) > epsilon) {
            // ersetze t durch Mittelwert von t und c/t
            t = (t + c/t) / 2.0;
        }
        StdOut.println(t);       // approximierte Quadratwurzel von c
    }
}

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.

Listing 3: ScalarProduct.java
import StdLib.StdOut;

/**
 * Demonstration der Modellierung von Vektoren mithilfe von Arrays.
 */
public class ScalarProduct {
    /**
     * Berechnung des Skalar-Produkts zweier fix codierter Vektoren.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        double[] v1 = {1.2, 2.8, 3.0, 4.0};  // erster Vektor
        double[] v2 = {3.0, 4.2, 3.1, 5.5};  // zweiter Vektor
        double sum = 0.0;                    // Vektorprodukt

        // elementweise Produkte addieren
        for (int i = 0; i < v1.length; i++)
            sum += v1[i] * v2[i];

        StdOut.println(sum);
    }
}

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.

Listing 4: Lotto.java
import StdLib.StdOut;

/**
 * Simulation der Lotto-Zahlen 6 aus 49.
 */
public class Lotto {
    /**
     * Aus einem Array mit 49 Zahlen werden 6 Zahlen zufällig,
     * ohne Zurücklegen, gezogen und ausgegeben.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        int N = 49,  M = 6;

        int[] a = new int[N];          // Initialisierung
        for (int i = 0; i < N; i++)
            a[i] = i+1;
        
        for (int i = 0; i < M; i++) {  // Mischen
            // tausche a[i] mit einem zufälligen Wert zur Rechten
            int r = i + (int) (Math.random() * (N - i));
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }

        
        for (int i = 0; i < M; i++)    // Ausgabe der ersten M Elemente
            StdOut.print(a[i] + "   ");
        StdOut.println();
    }
}

In Zeile 22 ist es erforderlich, die generierte Zufallszahl, eine Gleitkommazahl, in eine ganze Zahl umzurechnen.

  1. (Math.random() * (N - i)) erzeugt eine Zufallszahl im Intervall [0, N-i). Das ist ist eine Gleitkommazahl, mit einem Maximum kleiner als N-i.
  2. (int) schneidet die Nachkommastellen ab, sodass wir im Ergebnis, nach Addition von i, ganze Zahlen im Intervall [i, 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

Multiplikation von zwei quadratischen Matrizen
Abbildung 2

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).

Listing 5: MatrixMult.java
import StdLib.StdOut;

/**
 * Demonstration der Modellierung von Matrizen mittels
 * 2-dimensionaler Arrays.
 */
public class MatrixMult {
    /**
     * Zwei fix codierte (n x n)-Matrizen werden multipliziert und
     * das Ergebnis wird ausgegeben.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args)  {
        int[][] a = {{ 1,  2,  3,  4},
                    { 5,  6,  7,  9},
                    { 9, 10, 11, 12},
                    {13, 14, 15, 16}};
        int[][] b = {{17, 18, 19, 20},
                    {21, 22, 23, 24},
                    {25, 26, 27, 28},
                    {29, 30, 31, 32}};

        int n = a.length;           // Dimension abfragen
        int[][] c = new int[n][n];  // Speicher für Ergebnis

        // Matrix-Multiplikation
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = 0;
                for (int k = 0; k < n; k++)
                    c[i][j] += a[i][k] * b[k][j];
            }
        }

        // Ergebnis ausgeben
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                StdOut.printf("%6d ", c[i][j]);
            StdOut.println();
        }
    }
}

Zeichenkettenvergleich {sec-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.stdtools.StdIn liest eine Zeichenkette ein und liefert sie uns als ein Array von Zeichen zurück.

Listing 6: StrCompare.java
import StdLib.StdIn;
import StdLib.StdOut;
/**
 * Zeichenkettenvergleich auf Basis von Zeichen-Arrays.
 */
public class StrCompare {
    /**
     * Es werden zwei Zeichenketten interaktiv eingelesen und verglichen.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        char[] s1 = StdIn.readlnChars("1. Zeichenkette: ");
        char[] s2 = StdIn.readlnChars("2. Zeichenkette: ");
        
        StdOut.print(s1);
        int i;                       // Zeichenindex
        for (i = 0; i < s1.length && // solange s1 nicht am Ende
                    i < s2.length && // solange s2 nicht am Ende
                    s1[i] == s2[i];  // solange s1 und s2 gleich
                    i++)             // rücke ein Zeichen weiter
            ; /* leerer Schleifenrumpf */
        
        // Prüfung, weshalb die Schleife abgebrochen wurde
        if (i == s1.length && i == s2.length)
            StdOut.print(" = ");     // gleichzeitig zu Ende
        else if (i == s1.length)     // s1 kürzer als s2
            StdOut.print(" < ");
        else if (i == s2.length)     // s1 länger als s2
            StdOut.print(" > ");
        else if (s1[i] < s2[i])      // s1 kleiner als s2
            StdOut.print(" < ");
        else StdOut.print(" > ");    // s1 größer als s2
        StdOut.println(s2);
    }
}

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.

  1. 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.
  2. Wir beginnen bei der kleinsten bekannten Primzahl. Sie wird durch den Index-Wert 2 repräsentiert.
  3. 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.
  4. Wir wiederholen Schritt 3 mit dem nächsten Index, wenn dieser nicht bereits mit false markiert ist.

Das ist ein typischer „2-Zeigefinger-Algorithmus”. Der linke Zeigefinger geht elementweise durch das Array, während der rechte Zeigefinger die Vielfachen markiert.

Listing 7: Eratosthenes.java
import StdLib.StdOut;

/**
 * Sieb des Eratosthenes. 
 * 
 * Die Eingabe, bis zu welcher Zahl analysiert werden soll, erfolgt 
 * als Kommandozeilenargument.
 */
public class Eratosthenes {
    
    /**
     * Es wird eine positive Ganzzahl (größer gleich 2) eingelesen und 
     * es werden die Primzahlen bestimmt, die kleiner gleich dieser 
     * Eingabezahl sind.
     * 
     * @param args [0] - Zahl, bis zu der analysiert wird
     */
    public static void main(String[] args) {
        boolean[] prime;                    // Array von Wahrheitswerten
        int i, j;                           // Laufvariablen

        // Array beginnt bei 0, Eingabezahl soll inkludiert sein
        int N = Integer.parseInt(args[0]) + 1;

        // Array initialisieren: "Alle Zahlen sind Primzahlen"
        prime = new boolean[N];
        for (i = 2; i < N; i++) 
            prime[i] = true;

        // 2-Zeigefinger-Algorithmus
        for (i = 2; i < N; i++)            // linker Zeigefinger
            if (prime[i]) {                // wenn i Primzahl, dann
                StdOut.print(i + "  ");    // i ausgeben
                for (j = i*i; j < N; j+=i) // rechter Zeigefinger  
                    prime[j] = false;      // Vielfache j von i streichen
            }
        StdOut.println();
    }
}

Hinweis: Man mag geneigt sein, j in Zeile 36 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.

Listing 8: Josephus.java
import StdLib.StdOut;

/** 
 * Implementierung des <em>Josephus</em>-Problems mittels
 * eines Abzählreims.
 */
public class Josephus {
    /**
     * Die Parameter für Kinder- und Silbenanzahl des Abzählreims
     * werden als Kommandozeilenargumente übergeben.
     * 
     * @param args <br>
     * [0] - Anzahl der Kinder<br>
     * [1] - Anzahl der Silben
     */
    public static void main(String[] args) {
        int[] next;                          // Array für Kinder
        int i, index;                        // Laufvariablen
        int N = Integer.parseInt(args[0]);   // Anzahl Kinder
        int k = Integer.parseInt(args[1]);   // Anzahl Silben

        next = new int[N];                   // initiale Aufstellung
        for (i = 0; i < N; i++)
            next[i] = (i + 1) % N;           // Verweis auf nächstes Kind

        index = N - 1;                       // letztes Kind
        while (next[index] != index) {       // ungleich Nachfolger?
            for (i = 1; i < k; i++)          // Abzählreim
                index = next[index];

            StdOut.printf("Ausgeschieden: %2d\n", next[index]);
            next[index] = next[next[index]]; // neuer Nachfolger
        }
        StdOut.printf("Gewinner ist:  %2d\n", index);
    }
}

Die Formulierung next[i] = (i + 1) % N, Zeile 22, 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.stdtools.StdIn ein, die uns ein entsprechendes Array zurückgibt.

Listing 9: MinSearch.java
import StdLib.StdIn;
import StdLib.StdOut;

/**
 * Minimum-Suche in einem unsortierten Array ganzer Zahlen.
 */
public class MinSearch {
    /**
     * Es wird interaktiv eine Folge von ganzen Zahlen eingelesen, von
     * denen dann das Minimum bestimmt wird.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        int[] a = StdIn.readlnInts("Folge ganzer Zahlen: ");
        int index = 0;            // Index des
        int min = a[index];       // vorläufigen Minimums

        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {     // neues Minimum
                index = i;        // Index merken
                min = a[i];       // Minimum merken
            }
        }
        StdOut.printf("Minimum %d an Position %d\n", min, index);
    }
}

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.

Listing 10: LinSearch.java
import StdLib.StdIn;
import StdLib.StdOut;

/**
 * Lineare Suche in einem Array ganzer Zahlen.
 */
public class LinSearch {
    /**
     * In einer Folge ganzer Zahlen wird das erste Vorkommen einer 
     * einzelnen Zahl gesucht.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        int[] a = StdIn.readlnInts("Folge ganzer Zahlen: ");
        int x = StdIn.readlnInt("Zu suchende Zahl...: ");

        int i;  // Laufvariable
        for (i = 0; i < a.length && a[i] != x; i++)
            ; /* leere Anweisung */
        if (i == a.length) StdOut.println("Nicht gefunden");
        else               StdOut.println("Gefunden an Position " + i);
    }
}

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.

Listing 11: BinSearch.java
import StdLib.StdIn;
import StdLib.StdOut;

/**
 * Binäre Suche in einem aufsteigend geordneten Array ganzer Zahlen.
 */
public class BinSearch {
    /**
     * In einem <b>aufsteigend</b> geordneten Array ganzer Zahlen wird
     * eine interaktiv einzugebende Zahl gesucht.
     * 
     * @param args nicht genutzt
     */
    public static void main(String[] args) {
        int[] a = StdIn.readlnInts("Sortierte Folge ganzer Zahlen: ");
        int x = StdIn.readlnInt("Zu suchende Zahl.............: ");

        // Such-Indizes
        int lft = 0, rgt = a.length-1, mid = (rgt+lft)/2;

        while (lft <= rgt && a[mid] != x) {
            if (a[mid] < x) lft = mid+1;
            else            rgt = mid-1;
            mid = (lft+rgt)/2;
        }
        if (lft > rgt) StdOut.println("Nicht gefunden");
        else           StdOut.println("Gefunden an Position " + mid);
    }
}

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 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
$ _