Neueste Populär Trending
Suchalgorithmen: Just Keep Searching

» Suchalgorithmen: Min-/Max-Suche und Lineare Suche (Linear Search)

Ein typisches Beispiel für Suchprobleme ist die Exakte Suche. Bei der Exakten Suche sei eine endliche Folge von Elementen aus einer Menge M gegeben. Zusätzliche sei noch ein Element key aus der Menge M gegeben. Die Aufgabe ist nun das Element key in der Folge zu finden. Suchalgorithmen hierfür sind die Lineare Suche und die Binäre Suche, wobei letztere hier nicht behandelt wird.

Ein anderes Beispiel für ein Suchproblem ist die Min- bzw. Max-Suche. Hier sei eine endliche Folge von Elementen aus einer Menge M gegeben. Die Aufgabe hier ist es das größte Element max bzw. das kleinste Element min zu finden.

Um diese Probleme zu lösen gibt es die folgenden Suchalgorithmen.

Suchalgorithmen Übersicht

› Min-/Max-Suche

Als Voraussetzung für die Min-/Max-Suche muss eine totale Ordnung < auf M gegeben sein (Beispiele: natürliche Zahlen, ganze Zahlen, reelle Zahlen, Strings, ...). Totale Ordnung bedeutet also das zwei Elemente aus der Menge M vergleichbar sind. Als Eingabe für den Algorithmus haben wir also die Menge M mit totaler Ordnung < und als Ausgabe das maximale/minimale Element und wo es steht (d.h. den index).

def maxOfArray(A):
    """Durchlaufe nacheinander die Elemente der Menge und merke
    das jeweils größte Element.

    Args:
        A (list): Menge A

    Returns:
        tuple: max. von A und Index i, sodass 0 <= i <= len(A) und A[i]==max\
            oder 0,-1 falls A leer ist.
    """
    # abbruch, da leeres array.
    if len(A) == 0:
        return 0, -1

    currentMax = A[0]
    indexOfMax = 0

    # durchlaufe array und merke größtest element+index
    for i in range(1, len(A)):
        if A[i] > currentMax:
            currentMax = A[i]
            indexOfMax = i

    return currentMax, indexOfMax

if __name__ == '__main__':
    print(maxOfArray([2, 5, 8, 10, 1, 42, 6]))  # Ausgabe: (42, 5)

Die Min-Suche geht analog.

› Lineare Suche

Ist nichts über die (An-)Ordnung der Elemente in der Menge M bekannt, so kann nur die lineare Suche benutzt werden. Hierbei wird der key nacheinander mit jedem Element aus M verglichen bis das richtige Element gefunden wurde, anderenfalls taucht es nicht in der Menge auf.

def linSearch(A, key):
    """Lineare Suche.

    Args:
        A (list): Menge A.
        key (object): Element das gefunden werden soll.

    Returns:
        int: Index i, sodass 0 <= i <= len(A) und A[i]==key\
            oder -1 falls key nicht auftritt.
    """
    for i in range(len(A)):
        if A[i] == key:
            return i

    return -1

if __name__ == '__main__':
    print(linSearch([2, 5, 8, 10, 1, 42, 6], 10))  # Ausgabe 3

Literatur und Referenzen

Kommentar hinzufügen

Wir verwenden Cookies um Inhalte zu personalisieren und unsere Besucherstatistik zu führen. Bitte entscheiden Sie sich, ob Sie unsere Cookies akzeptieren möchten.