jario_
Zur Übersicht

Algorithmen und Datenstrukturen · Kapitel 1

Suchen

Ist ein Wert im Array, und wenn ja, wo? Diese Frage stellt fast jedes Programm, ob es eine Kundennummer nachschlägt oder einen Namen in einer Liste findet. In diesem Kapitel lernst du die zwei klassischen Verfahren kennen: die lineare und die binäre Suche. Und du siehst zum ersten Mal, wie man misst, wie schnell ein Algorithmus ist.

Lineare Suche

Die lineare Suche geht das Array von vorne nach hinten durch und vergleicht jedes Element mit dem gesuchten Wert. Beim ersten Treffer gibt sie den Index zurück. Kommt sie am Ende an, ohne etwas zu finden, gibt sie -1 zurück. -1 ist nie ein gültiger Index und eignet sich darum als Zeichen für „nicht gefunden“.

Die lineare Suche funktioniert mit jedem Array, sortiert oder nicht, und mit jedem Typ. Bei Strings vergleichst du dabei mit equals, nicht mit ==.

public class Main {    public static int indexOf(int[] numbers, int target) {        for (int i = 0; i < numbers.length; i++) {            if (numbers[i] == target) {                return i;            }        }        return -1;    }
    public static void main(String[] args) {        int[] numbers = {42, 7, 19, 3, 7};        System.out.println(indexOf(numbers, 7));        System.out.println(indexOf(numbers, 3));        System.out.println(indexOf(numbers, 99));    }}

Abwandlungen sind schnell gebaut: Für den letzten Treffer läuft die Schleife rückwärts, zum Zählen läuft sie ganz durch, und für Minimum oder Maximum merkst du dir den Index des bisher besten Elements.

Binäre Suche

Ist das Array aufsteigend sortiert, geht es viel schneller. Die binäre Suche schaut in die Mitte des Bereichs:

  • Ist der Wert dort gleich dem gesuchten, ist sie fertig.
  • Ist er kleiner, kann das Ziel nur rechts davon liegen: lo = mid + 1.
  • Ist er größer, kann es nur links davon liegen: hi = mid - 1.

lo und hi sind die Grenzen des Bereichs, der noch in Frage kommt, beide einschließlich. Die Schleife läuft, solange er nicht leer ist, also mit while (lo <= hi). Mit jedem Schritt halbiert sich der Bereich.

public class Main {    public static int binarySearch(int[] sorted, int target) {        int lo = 0;        int hi = sorted.length - 1;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            System.out.println("lo=" + lo + " mid=" + mid + " hi=" + hi);            if (sorted[mid] == target) {                return mid;            } else if (sorted[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return -1;    }
    public static void main(String[] args) {        int[] sorted = {3, 7, 19, 25, 42, 56, 80};        System.out.println("Found at " + binarySearch(sorted, 56));    }}

Dieselbe Idee geht auch rekursiv: Die Methode bekommt lo und hi als Parameter und ruft sich mit der passenden Hälfte selbst auf. Der Abbruchfall ist lo > hi (nicht gefunden) oder ein Treffer in der Mitte.

Laufzeit: O(n) und O(log n)

Wie schnell ein Algorithmus ist, misst man nicht in Sekunden, sondern daran, wie die Zahl der Schritte mit der Größe n der Eingabe wächst. Das schreibt man in O-Notation:

  • Die lineare Suche braucht im schlechtesten Fall n Vergleiche. Doppelt so viele Daten, doppelt so viele Schritte: O(n).
  • Die binäre Suche halbiert den Bereich bei jedem Schritt. Nach etwa log₂ n Schritten ist nur noch ein Element übrig: O(log n).

Bei einer Million Elementen sind das eine Million Vergleiche gegen etwa 20. Dafür muss das Array sortiert sein, und Sortieren kostet selbst Zeit (dazu mehr in den nächsten Kapiteln). Suchst du nur einmal, reicht oft die lineare Suche. Suchst du oft im selben Array, lohnt sich das Sortieren.

public class Main {    public static int linearSteps(int[] sorted, int target) {        int steps = 0;        for (int value : sorted) {            steps++;            if (value == target) {                break;            }        }        return steps;    }
    public static int binarySteps(int[] sorted, int target) {        int steps = 0;        int lo = 0;        int hi = sorted.length - 1;        while (lo <= hi) {            steps++;            int mid = lo + (hi - lo) / 2;            if (sorted[mid] == target) {                break;            } else if (sorted[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return steps;    }
    public static void main(String[] args) {        for (int n = 10; n <= 1_000_000; n *= 10) {            int[] sorted = new int[n];            for (int i = 0; i < n; i++) {                sorted[i] = 2 * i;            }            int target = sorted[n - 1];            System.out.println("n=" + n                    + "  linear: " + linearSteps(sorted, target)                    + "  binary: " + binarySteps(sorted, target));        }    }}

Suchen mit der Standardbibliothek

In echten Programmen schreibst du die Suche selten selbst. Arrays.binarySearch sucht binär in einem sortierten Array, List.indexOf und List.contains suchen linear in einer Liste.

Fehlt der Wert, liefert Arrays.binarySearch keine -1, sondern -(Einfügeposition) - 1. Die Einfügeposition ist die Stelle, an der der Wert stehen müsste, damit das Array sortiert bleibt. Im Beispiel gehört die 10 an Index 2, also kommt -3 heraus.

import java.util.Arrays;import java.util.List;
public class Main {    public static void main(String[] args) {        int[] numbers = {42, 7, 19, 3};        Arrays.sort(numbers);        System.out.println(Arrays.toString(numbers));        System.out.println(Arrays.binarySearch(numbers, 19));        System.out.println(Arrays.binarySearch(numbers, 10));
        List<String> names = List.of("Ali", "Mia", "Tom");        System.out.println(names.indexOf("Mia"));        System.out.println(names.contains("Eva"));    }}

Typische Fehler

  • Binäre Suche auf unsortierten Daten

    Die binäre Suche verlässt sich darauf, dass links von mid nur Kleineres und rechts nur Größeres steht. Ist das Array nicht sortiert, wirft sie keinen Fehler, sondern liefert einfach falsche Ergebnisse, etwa -1 für einen Wert, der da ist. Sortiere vorher oder nimm die lineare Suche.

  • Off-by-one in Bedingung und Grenzen

    Sind lo und hi beide einschließlich, muss die Schleife while (lo <= hi) heißen. Mit lo < hi wird das letzte verbliebene Element nie geprüft, und die Suche übersieht Werte am Rand. Genauso wichtig: lo = mid + 1 und hi = mid - 1. Mit lo = mid kann die Schleife endlos laufen, weil sich der Bereich nicht mehr verkleinert.

  • Überlauf bei (lo + hi) / 2

    Bei sehr großen Arrays kann lo + hi größer werden als der größte int-Wert und negativ werden. Dann ist mid ein ungültiger Index. Sicher ist:

    int mid = lo + (hi - lo) / 2;

    hi - lo ist nie größer als die Länge des Arrays, darum kann hier nichts überlaufen. Für Arrays in Übungsaufgaben ist beides richtig, in der Klausur macht die sichere Form aber einen guten Eindruck.