Lineare und binäre Suche

Einführung

Du suchst in einer langen Liste von Zahlen nach einem bestimmten Wert. Klick für Klick musst du jedes Element prüfen – das kann mühsam und langsam werden. Stell dir nun vor, die Liste ist sortiert: Mit der richtigen Methode kannst du den Suchaufwand drastisch verkürzen.

Lineare Suche (Seite für Seite blättern) vs. binäre Suche (gezielt in der Mitte aufschlagen) — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

In dieser Lerneinheit lernst du zwei zentrale Verfahren kennen: die lineare Suche, die jedes Element nacheinander prüft, und die binäre Suche, die den Suchbereich bei jedem Schritt halbiert.

Beide Verfahren sind Grundlagen der Informatik und helfen dir zu verstehen, wie unterschiedliche Algorithmen Effizienz und Laufzeit beeinflussen.

Lernziele

Nach dieser Einheit kannst du:

1. Die Funktionsweise der linearen Suche erklären und in Java implementieren.
2. Die binäre Suche nachvollziehen, inklusive der Berechnung der Mitte mit Ganzzahldivision.
3. Vor- und Nachteile beider Verfahren vergleichen und Einsatzszenarien begründet auswählen.
4. Die Komplexität (Big-O-Notation) von linearer und binärer Suche analysieren und deren Auswirkungen auf große Datenmengen einschätzen.

Überleitung

Die lineare Suche ist der einfachste Algorithmus zur Suche in einer Liste oder einem Array. Du prüfst nacheinander jedes Element, bis du den gesuchten Wert findest oder das Ende erreicht ist.

Schauen wir uns die Funktionsweise genauer an

Funktionsweise der linearen Suche

Die lineare Suche folgt einem klaren Ablauf. Du gehst systematisch von Anfang bis Ende durch die Daten.

1. Beginne am ersten Element.
2. Vergleiche das aktuelle Element mit dem gesuchten Wert.
3. Wenn beide übereinstimmen, gib den Index zurück.
4. Wenn nicht, gehe zum nächsten Element.
5. Wiederhole den Vorgang, bis das Element gefunden wurde oder das Ende erreicht ist.

Beispiel Schritt für Schritt

Angenommen, du hast das Array [5, 2, 8, 1, 9] und suchst nach der Zahl 8.

• Position 0: Wert 5 → 5 == 8? → Nein
• Position 1: Wert 2 → 2 == 8? → Nein
• Position 2: Wert 8 → 8 == 8? → Ja, gefunden!

Das Ergebnis ist: Element 8 gefunden an Position 2.

Java-Implementierung

Die lineare Suche lässt sich sehr einfach in Java programmieren:

public class LinearesSuchen {
    /**
     * Führt eine lineare Suche in einem Array durch.
     * @param array Das zu durchsuchende Array
     * @param zielwert Der gesuchte Wert
     * @return Index des gefundenen Elements oder -1, wenn nicht gefunden
     */
    public static int linearesuche(int[] array, int zielwert) {
        // Durchlaufe das Array von Anfang bis Ende
        for (int i = 0; i < array.length; i++) {
            // Vergleiche aktuelles Element mit Zielwert
            if (array[i] == zielwert) {
                return i; // Element gefunden, Index zurückgeben
            }
        }
        // Falls Schleife endet, wurde kein Treffer gefunden
        return -1; // Element nicht gefunden
    }
 
    // Beispiel für die Verwendung
    public static void main(String[] args) {
        int[] zahlen = {5, 2, 8, 1, 9};
        int gesuchteZahl = 8;
        int ergebnis = linearesuche(zahlen, gesuchteZahl);
 
        if (ergebnis != -1) {
            System.out.println("Zahl " + gesuchteZahl + " gefunden an Position: " + ergebnis);
        } else {
            System.out.println("Zahl " + gesuchteZahl + " nicht gefunden!");
        }
    }
}

In der Methode linearesuche wird das Array mit einer Schleife vollständig durchlaufen. Jedes Element wird mit dem Zielwert verglichen. Sobald ein Treffer gefunden wird, wird der Index sofort zurückgegeben. Ist kein Treffer vorhanden, liefert die Methode den Wert -1, was signalisiert, dass das Element nicht existiert.

Erläuterung des Codes:

• linearesuche(int[] array, int zielwert): Nimmt das Array und den gesuchten Wert entgegen und liefert den Index zurück.
• for (int i = 0; i < array.length; i++): Durchläuft alle Positionen von 0 bis array.length - 1 in fester Reihenfolge.
• if (array[i] == zielwert) { return i; }: Vergleicht das aktuelle Element mit dem Zielwert und bricht bei Erfolg sofort ab.
• return -1;: Wird nur erreicht, wenn in keiner Position eine Übereinstimmung gefunden wurde.
• main(...): Legt ein Beispiel-Array an, ruft die Suche auf und gibt je nach Ergebnis entweder den Index oder eine Fehlermeldung aus.

Die Methode arbeitet rein iterativ und benötigt keinen zusätzlichen Speicher außer wenigen Variablen. Durch den frühzeitigen Abbruch ist die Laufzeit bei Treffern am Anfang deutlich geringer als im Worst Case.

Vorteile und Nachteile

Die lineare Suche ist leicht einsetzbar, aber nicht für jede Datengröße sinnvoll. Die Tabelle fasst die wichtigsten Vor- und Nachteile zusammen.

Kategorie	Punkt	Erläuterung
Vorteil	Einfachheit	Die Implementierung ist kurz und fehlerarm.
Vorteil	Keine Sortierung nötig	Funktioniert direkt auf unsortierten Datenstrukturen.
Vorteil	O(1) Zusatzspeicher	Es werden nur wenige Hilfsvariablen benötigt.
Nachteil	Keine Nutzung von Struktur	Auch in fast sortierten Daten keine Beschleunigung.
Nachteil	Linear skalierend	Verdoppelt sich die Datenmenge, verdoppelt sich die Prüfanzahl.

Für kleine oder selten durchsuchte Datenmengen ist die Methode praktikabel. Bei häufigen Suchen in großen Datenbeständen solltest du effizientere Verfahren einsetzen.

Wann solltest du die lineare Suche verwenden?

Die lineare Suche eignet sich besonders in folgenden Situationen:

• Kleine Arrays (unter 100 Elemente).
• Unsortierte Daten.
• Einmalige oder seltene Suchoperationen.
• Einfache Anwendungen, bei denen Effizienz keine große Rolle spielt.

Zeitkomplexität (Big-O-Notation)

Die Laufzeit der linearen Suche hängt von der Größe des Arrays ab. Im schlimmsten Fall wird jedes Element überprüft.

• Best Case: O(1) → Wenn das gesuchte Element direkt am Anfang steht.
• Worst Case: O(n) → Wenn das gesuchte Element am Ende steht oder gar nicht vorhanden ist.
• Average Case: O(n) → Im Durchschnitt wird etwa die Hälfte aller Elemente geprüft.

Das bedeutet: Je größer die Datenmenge, desto länger dauert die lineare Suche. Sie ist also nicht effizient für sehr große Arrays, aber für kleine, überschaubare Datenmengen völlig ausreichend.

Komplexität (Big-O-Notation)

Die lineare Suche hat im Worst- und Durchschnittsfall eine Laufzeit O(n), weil im ungünstigsten Fall jedes der n Elemente geprüft wird.

Im Best Case ist die Laufzeit O(1), wenn das gesuchte Element gleich am ersten Index liegt. Der Zusatzspeicher bleibt O(1), da nur Zähl- und Vergleichsvariablen verwendet werden.

Diese Eigenschaften erklären, warum die Methode bei kleinen Datenmengen unproblematisch ist. Bei wachsender Datenmenge steigen die Kosten jedoch proportional zur Größe der Eingabe.

⏳ Lädt Dataview-Inhalt...

Binäre Suche (Binary Search)

Die binäre Suche ist ein effizienter Suchalgorithmus, der nach dem Teile-und-herrsche-Prinzip arbeitet. Voraussetzung ist, dass die Daten sortiert sind.

Funktionsweise der binären Suche

Bei der binären Suche halbierst du den Suchbereich bei jedem Schritt. Dadurch wird die Menge der zu prüfenden Elemente sehr schnell kleiner.

1. Bestimme das mittlere Element des Arrays.
2. Vergleiche dieses mit dem gesuchten Wert.
3. Wenn beide gleich sind, ist die Suche erfolgreich.
4. Wenn der Zielwert kleiner ist, suche in der linken Hälfte weiter.
5. Wenn der Zielwert größer ist, suche in der rechten Hälfte weiter.
6. Wiederhole den Vorgang, bis das Element gefunden ist oder kein Bereich mehr übrig bleibt.

Beispiel Schritt für Schritt

Gegeben ist das sortierte Array [1, 3, 5, 7, 9, 11, 13, 15].

Wichtig ist: Die Indizes beginnen bei 0. Das bedeutet, das erste Element hat Index 0 und das letzte Element hat Index 7.

Hinweis: In Java wird bei der Berechnung der Mitte immer Ganzzahldivision verwendet. Das bedeutet, Nachkommastellen werden abgeschnitten. Beispiel: (0 + 7) / 2 = 3,5, Ergebnis ist 3. Dadurch wird immer der nächstkleinere ganzzahlige Index verwendet.

• Suche nach 7:

  • Gesamtes Array: [1, 3, 5, 7, 9, 11, 13, 15].
  • Mitte wird berechnet als (0 + 7) / 2 = 3. Der Index 3 enthält den Wert 7.
  • 7 == 7 → gefunden!

• Suche nach 11:

  • Gesamtes Array: [1, 3, 5, 7, 9, 11, 13, 15].
  • Mitte = (0 + 7) / 2 = 3. Wert an Index 3 ist 7.
  • 11 > 7 → wir betrachten die rechte Hälfte [9, 11, 13, 15] (Indizes 4 bis 7).
  • Neue Mitte = (4 + 7) / 2 = 11 / 2 = 5
  • 11 == 11 → gefunden!

Die Mitte ist also nicht immer dasselbe Element, sondern hängt vom aktuellen Suchbereich ab. Dadurch wird das Array bei jedem Schritt halbiert, bis das Ergebnis vorliegt.

Java-Implementierung

Die binäre Suche lässt sich in Java so programmieren:

public class BinaereSuche {
    /**
     * Führt eine binäre Suche in einem SORTIERTEN Array durch.
     * @param array Das sortierte Array
     * @param zielwert Der gesuchte Wert
     * @return Index des gefundenen Elements oder -1, wenn nicht gefunden
     */
    public static int binaeresuche(int[] array, int zielwert) {
        int links = 0; // Start des Suchbereichs
        int rechts = array.length - 1; // Ende des Suchbereichs
 
        // Solange der Suchbereich gültig ist
        while (links <= rechts) {
            int mitte = (links + rechts) / 2; // Berechne die Mitte
 
            if (array[mitte] == zielwert) {
                return mitte; // Element gefunden
            }
 
            if (array[mitte] > zielwert) {
                rechts = mitte - 1; // Suche links weiter
            } else {
                links = mitte + 1; // Suche rechts weiter
            }
        }
        return -1; // Element nicht gefunden
    }
 
    // Beispiel für die Verwendung
    public static void main(String[] args) {
        int[] sortierteZahlen = {1, 3, 5, 7, 9, 11, 13, 15};
        int gesuchteZahl = 7;
        int ergebnis = binaeresuche(sortierteZahlen, gesuchteZahl);
 
        if (ergebnis != -1) {
            System.out.println("Zahl " + gesuchteZahl + " gefunden an Position: " + ergebnis);
        } else {
            System.out.println("Zahl " + gesuchteZahl + " nicht gefunden!");
        }
    }
}

Erläuterung des Codes: Die Methode verwaltet einen linken und rechten Rand des Suchbereichs. Mit jedem Schritt wird die Mitte berechnet und der Bereich halbiert. Durch die Anpassung von links und rechts wird der Suchraum immer kleiner, bis das Element gefunden oder ausgeschlossen ist.

Vorteile und Nachteile

Die binäre Suche ist sehr effizient, hat aber wichtige Einschränkungen.

Kategorie	Punkt	Erläuterung
Vorteil	Sehr schnell	Halbiert den Suchbereich bei jedem Schritt.
Vorteil	Gute Skalierbarkeit	Auch bei Millionen von Elementen bleibt die Suche effizient.
Vorteil	Vorhersagbare Performance	Immer logarithmische Laufzeit.
Nachteil	Array muss sortiert sein	Ohne Sortierung funktioniert die Methode nicht.
Nachteil	Zusätzlicher Aufwand	Falls die Daten zuerst sortiert werden müssen.
Nachteil	Komplexere Implementierung	Deutlich aufwendiger als lineare Suche.

Für häufige Suchen in großen Datenmengen ist die binäre Suche optimal. Bei kleinen, unsortierten Daten lohnt sich der Sortieraufwand dagegen nicht.

Komplexität (Big-O-Notation)

Die binäre Suche hat im Worst- und Durchschnittsfall O(log n), da der Suchbereich bei jedem Schritt halbiert wird. Im Best Case O(1), wenn das mittlere Element sofort dem Zielwert entspricht. Der Speicherbedarf ist O(1), da nur wenige Variablen für Indizes und Mitte benötigt werden.

Diese Eigenschaften machen die binäre Suche zu einer der effizientesten Methoden, solange du mit sortierten Daten arbeitest.

⏳ Lädt Dataview-Inhalt...

Zusammenfassung

Zusammenfassung:

Lineare Suche

Die lineare Suche ist der einfachste Suchalgorithmus. Du durchläufst jedes Element eines Arrays oder einer Liste der Reihe nach, bis du den gesuchten Wert findest oder das Ende erreicht ist.

• Funktionsweise: Vergleicht von vorn bis hinten jedes Element mit dem Zielwert.
• Beispiel: In [5, 2, 8, 1, 9] wird die 8 bei Index 2 gefunden.
• Java-Implementierung: Eine einfache Schleife prüft jedes Element; Rückgabe des Index oder -1, wenn nicht vorhanden.
• Vorteile: Sehr leicht zu verstehen, funktioniert auch mit unsortierten Daten, benötigt keinen zusätzlichen Speicher.
• Nachteile: Sehr langsam bei großen Datenmengen, im Worst Case Prüfung aller Elemente.
• Komplexität: O(n) im Worst und Average Case, O(1) im Best Case; Speicherbedarf O(1).

Binäre Suche

Die binäre Suche ist deutlich effizienter, setzt aber sortierte Daten voraus. Sie halbiert den Suchbereich bei jedem Schritt.

• Funktionsweise: Berechnet die Mitte des aktuellen Bereichs, vergleicht mit dem Zielwert, und durchsucht nur die linke oder rechte Hälfte weiter.
• Beispiel: In [1, 3, 5, 7, 9, 11, 13, 15] wird die 7 sofort an Index 3 gefunden. Bei der Suche nach 11 wird der Bereich zunächst rechts eingegrenzt und dann an Index 5 gefunden. Dabei wird in Java die Mitte durch Ganzzahldivision berechnet, Nachkommastellen werden abgeschnitten.
• Java-Implementierung: Mit einer Schleife und den Grenzen links und rechts wird der Suchbereich angepasst; Rückgabe des Index oder -1, wenn nicht vorhanden.
• Vorteile: Sehr schnell bei großen Daten, halbiert den Suchraum pro Schritt, vorhersagbare logarithmische Performance.
• Nachteile: Funktioniert nur auf sortierten Daten, erfordert Sortieraufwand, etwas komplexere Implementierung.
• Komplexität: O(log n) im Worst und Average Case, O(1) im Best Case; Speicherbedarf O(1).

Ausblick:

In der nächsten Lerneinheit lernst du den Bubble-Sort-Algorithmus kennen – ein einfaches, aber grundlegendes Verfahren zum Sortieren von Daten. Du erfährst, wie Elemente durch wiederholte Vergleiche und Vertauschen in die richtige Reihenfolge gebracht werden und welche Vor- und Nachteile dieser Ansatz im Vergleich zu effizienteren Sortierverfahren hat.

---