Suche

Suche ist der Vorgang, festzustellen, ob ein bestimmtes Element existiert und welche genaue Position es innerhalb einer Datenmenge hat. Sie ist eine grundlegende Operation, die an fast allen Programmen beteiligt ist.


Vergleich von drei Suchalgorithmen

Komplexitätsvergleich von Suchalgorithmen — Anzahl der Operationen bei n=1000
Vergleichszusammenfassung von drei Suchalgorithmen

Lineare Suche O(n)

Erfordert keine sortierten Daten

Element für Element vergleichen, einfach und zuverlässig

Geeignet für: kleine oder ungeordnete Datenmengen

Binäre Suche O(log n)

Erfordert sortierte Daten

Halbiert jedes Mal den Bereich, wodurch die Hälfte entfällt

Geeignet für: allgemeine Lösung für sortierte Daten

Interpolationssuche O(log log n)

Erfordert sortierte Reihenfolge + gleichmäßige Verteilung

Schätzt die Position anhand des Wertverhältnisses

Geeignet für: optimal, wenn die Daten gleichmäßig verteilt sind

Lineare Suche

Vergleicht eins nach dem anderen, beginnend beim ersten Element, bis das Ziel gefunden ist oder die Liste erschöpft ist. Erfordert keine sortierten Daten. Zeitkomplexität O(n).

Binäre Suche

Erfordert, dass die Daten sortiert sind. Vergleicht jedes Mal mit dem mittleren Element und halbiert den Suchbereich. Zeitkomplexität O(log n).

Interpolationssuche

Eine Optimierung der binären Suche. Anstatt den Mittelpunkt zu nehmen, schätzt sie die mögliche Position basierend auf dem Zielwert. Wenn die Daten gleichmäßig verteilt sind, kann sie O(log log n) erreichen.

Beispiel

#include <stdio.h>

/* Lineare Suche: O(n), erfordert keine sortierte Reihenfolge */
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

/* Binäre Suche: O(log n), erfordert, dass das Array sortiert ist (aufsteigend) */
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;  /* Berechnung zur Vermeidung von Überlauf */
        if (arr[mid] == target) return mid;    /* Gefunden */
        if (arr[mid] < target)
            left = mid + 1;   /* Das Ziel ist in der rechten Hälfte */
        else
            right = mid - 1;  /* Das Ziel ist in der linken Hälfte */
    }
    return -1;  /* Nicht gefunden */
}

/* Interpolationssuche: durchschnittlich O(log log n), erfordert gleichmäßig verteilte Daten */
int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        /* Interpolationsformel: Position basierend auf der proportionalen Größe des Wertes schätzen */
        int pos = low + ((target - arr[low]) * (high - low))
                        / (arr[high] - arr[low]);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int n = 9;

    printf("Lineare Suche 50: Index %d\n", linearSearch(arr, n, 50));      /* Ausgabe: 4 */
    printf("Binäre Suche 50: Index %d\n", binarySearch(arr, 0, n-1, 50)); /* Ausgabe: 4 */
    printf("Interpolationssuche 50: Index %d\n", interpolationSearch(arr, n, 50)); /* Ausgabe: 4 */
    return 0;
}

Zusammenfassung des Komplexitätsvergleichs

AlgorithmusZeitkomplexitätErfordert sortierte DatenGeeignete Szenarien
Lineare SucheO(n)neinKleines Datenvolumen oder unsortiert
Binäre SucheO(log n)JaSortierte Arrays, allgemein und effizient
InterpolationssucheO(log log n)DurchschnittJaSpezifische Szenarien mit gleichverteilten Daten
Andere Erweiterungen