Lineare Suche

Bei der Linearen Suche wird über jedes Element in der Liste gelaufen und mit dem gesuchten Element verglichen. Wenn die Elemente gleich sind, wird der Index zurück gegeben. Wenn kein Element gefunden wird, wird -1 zurück gegeben.

graph TD Z([Start]) --> A[index=0] A --> B{ index < a.length } B --> |True| C{"a[index] == searched"} B --> |False| F([Return -1]) C --> |False| D[index += 1] C --> |True| E(["Return a[index]"]) D --> B

Java Implementierung

public static int suche(int[] a, int value)
{
    for (int i=0; i<a.length; i++)
    {
        if(a[i] == value) return i;
    }
    return -1;
}

Binäre Suche

Der Grundgedanke geht davon aus, dass die zu durchuchende Liste schon im vorhinein sortiert ist. Die binäre Suche sucht sich das mittlere Element in der durchuchende Menge aus und vergleicht es mit dem gesuchten Wert. Wenn dieser direkt gleich dem gesuchten Wert ist, wird der index zurück gegeben. Wenn der gesuchte wert größer ist, dann wird die Rechte Hälfte der Bereichs genau nach diesem Schema noch einmal durchsucht. Beim kleinern passiert das gleiche mit der linken Hälfte.

graph TD A([Start]) --> B[start=0
end=a.length-1] B --> C{ start <= end } C --> |True| D["mid = (start+end)/2"] D --> E{"a[mid] == searched"} E --> |True| F[/Return mid/] E --> |False| G{"a[mid] < n"} G --> |True| H[start = mid+1] H --> C G --> |False| I[end = mid+1] I --> C F --> J([End]) C --> |False| K[/return -1/] K --> J

Java Implementierung

public static int binaereSuche(int[] array, int key){       //binäre Suche
    int rechts = array.length-1;
    int links = 0;
    if(key < array[links] || key > array[rechts])return -1;
    while (links < rechts)
    {   
        int index = links + (int) ((rechts-links) / 2);
        if(array[index] == key) return index;
        if(array[index] < key)
        {
            // Zähle Hoch
            links = index + 1;
        } else {
            // Zähle runter
            rechts = index - 1;
        }
    }
    if(links == rechts && array[links] == key) return key;
    return -1;
}

Vergleich der Komplexitäten

Die Lineare Suche hat eine Komplexität im worst case von O(n), wohingegen die binäre Suche eine Komplexität O(log(n)) hat, was eine deutliche Verbesserung ist.