Wikiversity

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Sequentielle Suche

< Kurs:Algorithmen und Datenstrukturen | Vorlesung


Startseite
Vorlesung


Sequentielle Suche

Bearbeiten

Dieses Kapitel handelt von der sequentiellen Suche. Die Idee dieses Suchalgorithmus ist, dass zuerst das erste Elemente der Liste mit dem gesuchten Elemente verglichen wird, wenn sie übereinstimmen wird der aktuelle Index zurückgegeben. Wenn nicht wird der Schritt mit dem nächsten Element wiederholt. Sollte das gesuchte Element bis zum Ende der Folge nicht gefunden werden, war die Suche erfolglos und -1 wird zurückgegeben.

Algorithmus

Bearbeiten 
 
int SeqSearch(int[] F, int k) {
   / * output: Position p  (0 ≤ p ≤ n-1) */ 
} 
 int n = F.length;
 for (int i = 0; i < n; i++) { 
    if (F[i] == k) {
          return i; 
 }  
 return -1;  }

Dabei ist Int[] die sortierte Folge von int, int k der Suchschlüssel und die Folge F hat die Länge n.

Aufwands Analyse

Bearbeiten

Das Terminierungs-Theorem besagt, dass der Algorithmus SeqSearch für eine endliche Eingabe nach endlicher Zeit terminiert. Das Korrektheits-Theorem besagt, falls das Array F ein Element k enthält, gibt SeqSearch(F,k) den Indes des ersten Vorkommens von k zurück. Ansonsten gibt SeqSearch(F,k) den Wert -1 zurück Im besten Fall beträgt die Anzahl der Vergleiche 1, das heißt direkt bei dem ersten Suchdurchlauf wird der Suchschlüssel gefunden. Im schlechtesten Fall beträgt die Anzahl der Vergleiche n, das heißt im letzten Suchdurchlauf wird der Suchschlüssel gefunden. Der Durchschnitt bei einer erfolgreichen Suche beträgt (n+1)/2 und der Durchschnitt einer erfolglosen Suche n. Die Folgen müssen nicht sortiert sein. Der Algorithmus SeqSearch hat also eine Worst-Case Laufzeit von  .

Sequentielle Suche in Java

Bearbeiten 
 
public class SequentialSearch{
     public final static int NO_KEY = -1;

static int SeqSearch(int[] F, int k) {
   for (int i = 0; i < F.length; i++) 
   if (F[i] == k) 
         return i;
   return NO_KEY; 
}
 public static void main(String[ ] args){
    if (args.length != 1) {
           System.out.println(''usage: SequentialSearch 
             <key>'');
    return;
    }

    int[ ] f = {2, 4, 5, 6, 7, 8, 9, 11};
    int k = Integer.parseInt(args[0]);
    System.out.println(''Sequentiell:“+seqSearch(f,k));
 }
}

In der Klasse SeqSearch ist eine Konstante NO_KEY definiert, die als Ergebnis zurückgegeben wird, wenn der gesuchte Wert nicht im Feld gefunden wurde. Die Methode search wird schließlich in der Klassenmethode main aufgerufen, um das Feld f nach dem Schlüsselwert k zu durchsuchen. Dieser Wert ist als Parameter beim Programmaufruf anzugeben. Da die Programmparameter als Feld args von Zeichenketten übergeben werden, ist zuvor noch eine Konvertierung in einen int-Wert mit Hilfe der Methode parseInt der Klasse java.lang.Integer vorzunehmen. Somit bedeutet der Programmaufruf "java SeqSearch 4" die Suche nach dem Wert 4 in der gegebenen Folge. Der Aufruf erfolgt mit java SequentialSearch 4

Literatur

Bearbeiten

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.1.1 zu finden.


     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Sequentielle_Suche&oldid=628947“