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
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
/* 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
| Algorithmus | Zeitkomplexität | Erfordert sortierte Daten | Geeignete Szenarien |
|---|---|---|---|
| Lineare Suche | O(n) | nein | Kleines Datenvolumen oder unsortiert |
| Binäre Suche | O(log n) | Ja | Sortierte Arrays, allgemein und effizient |
| Interpolationssuche | O(log log n)Durchschnitt | Ja | Spezifische Szenarien mit gleichverteilten Daten |