Suchen

Lineare Suche

Bei der linearen Suche wird das Feld von vorn nach hinten sequentiell solange durchsucht, bis das gewünschte Element gefunden wird (erfolgreiche Suche) oder das Feld erfolglos vollständig abgesucht wurde (erfolglose Suche). Es ist leicht einzusehen, dass die lineare Suche lineare Laufzeit besitzt.

Als Konvention gibt die Methode hier nicht nur die Erfolgsmeldung aus (true/false), sondern die Position des gefunden Elements bzw. -1 im Falle der erfolglosen Suche.

public int starteLineareSuche(int[] array, int key) { 

    for (int i=0; i<array.length; i++) {

        if (array[i]==key) {
            return i;
        }

    }

    return -1;
}

Binäre Suche

Die binäre Suche setzt ein bereits sortiertes Feld voraus (vgl. nächster Abschnitt Sortieren). Diese Sortierung wird durch die Idee der Intervallhalbierung ausgenutzt. In jedem Durchlauf wird die mittlere Position des verbleibenden Suchraums bestimmt. Ist das gesuchte Element an dieser Stelle vorhanden, so wird die Suche erfolgreich beendet. Ist das gesuchte Element kleiner, so kann der Suchraum auf alle Feldelemente links von der mittleren Position eingeschränkt werden. Ist das Element größer, so kann der Suchraum entsprechend auf alle Feldelemente rechts von der mittleren Position eingeschränkt werden. Sollten sich die Suchraumgrenzen gegenseitig überholen (l>r), so wird die Suche erfolglos abgebrochen.

Durch die Intervallhalbierung ist eine logarithmische Laufzeit bedingt, die viel besser als eine lineare Laufzeit einzustufen ist. Allerdings darf nicht vergessen werden, dass der zusätzliche Aufwand der Sortierung ebenfalls Laufzeit kostet.

public int starteBinaereSuche(int[] array, int key) {

    // Lege die Bereichsgrenzen fest
    int n = array.length;
    int m;

    int l = 0;
    int r = n-1;

    while (l<=r) {

        // Bestimme Mitte 
        m = (l+r) / 2;

        // Unterscheide drei Fälle

        // 1. Fall: GEFUNDEN
        if (array[m] == key) { 
            return m;
        }

        // 2. Fall: Suche LINKS weiter
        else if (key < array[m]) { 
            r = m-1;
        }

        // 3. Fall: Suche RECHTS weiter
        else { 
            l = m+1;
        }

    }

    return -1;

}

results matching ""

    No results matching ""