SuchAlgorithmen

Question 1

Vorlesung

Implementierung - Binäre Suche

Answer 1

int binarySearch(Data[] s, Key x, int left, int right ) {
// Initialisierung
    int p = (left + right) / 2;
    int c = s[p].key.compareTo(x);
    // Trivialfall: Element gefunden
    if (c == 0) return p;
// Trivialfall: Suche erfolglos
    if (left == right) return -1;
// Rekursion (und Reduktion)
    if (c > 0) {
        if (p > left) return binarySearch(s, x, left, p-1);
        else return -1;
    } else {
       if (p < right) return binarySearch(s, x, p+1, right);
        else return (-1);
    }
}

Question 2

Klausuraufgabe SS18

Zu welcher Komplexitätsklasse gehören die schnellsten Such-Algorithmen, wenn die Daten in
folgenden Datenstrukturen vorliegen?

• lineare, unsortierte verkettete Liste:
• sortierte Reihung (Array):
• Halde:

Answer 2

• lineare, unsortierte verkettete Liste:
lineare Suche O(n)

• sortierte Reihung (Array):
binäre Suche O(log n)

• Halde:
lineare Suche O(n)

Question 3

Klausuraufgabe SS16

Zu welcher Komplexitätsklasse gehören die schnellsten Such-Algorithmen, wenn die Daten in
folgenden Datenstrukturen vorliegen?

• lineare, unsortierte verkettete Liste:
• sortierte Reihung (Array):
• Halde:

Answer 3

• lineare, unsortierte verkettete Liste:
lineare Suche O(n)

• sortierte Reihung (Array):
binäre Suche O(log n)

• Halde:
lineare Suche O(n)

Question 4

KLAUSURAUFGABE WS15

Welche der folgenden Methoden ist/sind für das Suchen in sortierten Reihungen (Arrays)
geeignet und hat/haben die im Mittel geringste Komplexität?

Merge Sort
Quicksort
lineare Suche
binäre Suche

Answer 4

binäre Suche

Question 5

KLAUSURAUFGABE WS15

Welche der folgenden Komplexitätsklassen gibt das beste im Mittel (average case) erreichbare
asymptotische Verhalten für vergleichsbasiertes Suchen an?

O(log n)
O(n log n)
O(n)
O(n^2)
O(n^3)
O(2^n)

Answer 5

eigene Lösung

O(log n) (binäre Suche)