Die sequentielle Suche beruht auf dem naiven Ansatz einen Datenbestand vollständig zu durchsuchen bis das passende Element gefunden wird. Dieses Verfahren nennt man auch erschöpfende Suche oder im englischen das Greedy-Schema (engl. für gefräßig). Der Algorithmus für das Durchsuchen eines Felds ist der folgende:
- Spezifiziere Suchschlüssel
- Vergleiche jedes Element mit dem Suchschlüssel
- Erfolgsfall: Liefere Indexposition beim ersten Auffinden des Objekts und beende das Suchen
- Kein Erfolg: Gehe zum nächsten Objekt und vergleiche es.
- Gib eine Meldung über das erfolglose Suchen zurück wenn das Ende des Datenbestands erreicht wurde, ohne daß, das Objekt gefunden wird. Dies kann eine java-Ausnahme sein oder ein spezieller Rückgabewert (z.Bsp .1)
Der Aufwand für diesen Algorithmus ist linear, also O(n). Die Anzahl der nötigen Vergleichsoperationen hängt direkt von der Anzahl der Elemente im Datenbestand ab. Im statischen Mittel sind dies n/2 Vergleiche.
Sequentielle Suche in einem unsortierten Datenbestand
In diesem Fall muss bei jeder Suche der gesamte Datenbestand durchlaufen werden bis ein Element gefunden wurde
Beispiel einer Javaimplementierung
Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert -1 zurück wenn kein Ergebnis gefunden wird.
public static int sequentielleSuche() (int[] feld, int schluessel) { int suchIndex = 0; while (suchIndex< feld.length && feld[suchIndex] != schluessel) suchIndex++; if (suchIndex == feld.length) suchindex = -1; // Nichts gefunden return suchindex; }
Sequentielle Suche in einem sortierten Datenbestand
Bei einem sortierten Datenbestand kann man die Suche optimieren in dem man sie abbricht so bald man weiß, das die folgenden Elemente alle größer bzw. kleiner als das gesucht Element sind. Man muss also nicht das Feld vollständig durchlaufen. Hierdurch lässt sich Zeit sparen. Der durchschnittliche Aufwand von n/2 bleibt jedoch ein linearer Aufwand.
Beispiel einer Javaimplementierung
Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert -1 zurück wenn kein Ergebnis gefunden wird.
public static int sequentielleSuche() (int[] feld, int schluessel) int suchIndex = 0; while (suchIndex< feld.length && feld[suchIndex] < schluessel) suchIndex++; if ((suchindex < feld.length) && (feld[suchIndex] == feld[schluessel])) return suchindex; // Erfolg else return -1; //kein Erfolg }
- Printer-friendly version
- Log in to post comments
- 25257 views