Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Suche

Einleitung Suchen

In diesem Kapitel geben wir einen Überblick über das Thema Suchen. Suchprobleme sind eine der häufigsten Probleme in der Informatik. Man kann in sortierten Folgen suchen, Zeichenketten im Text suchen, Dokumente in Textkorpora suchen, oder allgemeine Lösungen von Problemräumen, wie der Spielbaumsuche oder der Plansuche, suchen. Hier behandeln wir zunächst die Suche in sortierten Folgen.

Motivation

Beim Suchen wiederholt man häufig sehr nützliche Beispielalgorithmen, oder lernt diese sogar neu kennen. Außerdem dient es der Vorbereitung der theoretischen Betrachtungen zur Komplexität von Algorithmen. Des weiteren dient es der informellen Diskussion von Entwurfsentscheidungen.

Suchen in sortierten Folgen

• Annahme:

Die Folge F ist ein Feld mit numerischen Werten. Dazu ist die Folge sortiert, das heißt, wenn i<j, dann ist F[i]<F[j]. Auf das i-te Element hat man Zugriff über F[i]. Es wird nur der Suchschlüssel berücksichtigt.

Ein Beispiel ist ein Telefonbuch, in dem wir nach Namen suchen möchten. Doch wie repräsentiert man diese Daten?

Einschub lineare Datenstrukturen

Definition

Eine lineare Datenstruktur L ist eine Sequenz $L=(a_{1}...,a_{n})$. Die lineare Datenstruktur ordnet Elemente (entweder primitive Datentypen oder komplexere Datenstrukturen) in einer linearen Anordnung an.

Beispiel

Zahlenfolgen

5

4

6

1

3

2

Strings

L

I

N

E

A

R

Atomare Operationen

Zu den Operationen gehören Lesen mit

• get(i): Element an Position i lesen
• first(): erstes Element lesen
• last(): letztes Element lesen
• next(e): Element nach Element e lesen

und Schreiben mit

• set(i,e): Element an Position i auf e setzen
• add(i,e): Element e an Position i einfügen
• del(i): Element an Position i löschen

Arrays und Listen

Es gibt zwei Möglichkeiten lineare Datenstrukturen zu realisieren. Entweder Arrays oder (verlinkte) Listen. Arrays belegen einen zusammenhängenden Bereich im Speicher. Elemente einer verlinkten Liste können beliebig verteilt sein. Ob zur Realisierung einer linearen Datenstruktur ein Array oder eine Liste verwendet wird, hängt von der Anwendung ab. Arrays werden meist für statische Datenstrukturen verwendet, d.h. wenn die Länge des Arrays nicht verändert wird. Listen werden meist für dynamische Datenstrukturen verwendet, d.h. wenn die Länge variabel ist. Zu den positiven Eigenschaften von Arrays zählen der schneller Zugriff auf Einzelelemente durch den Index. Zu den negativen Eigenschaften von Arrays zählen das sehr aufwändige Einfügen der Elemente. Zu den positiven Eigenschaften von Listen zählen die relativ effiziente Manipulation, zu den negativen Eigenschaften der ineffiziente Direktzugriff.

Einfache verlinkte Liste von Zahlen in Java

public class IntegerList { 
  private class IntegerListElement{ 
   int value; 
   IntegerListElement next; 
  } 
 
  IntegerListElement first; 
  int size = 0; 
     private IntegerListElement getElement(int i){ 
   if(i+1 > size)  
    throw new IllegalArgumentExcepHon(); 
   int idx = 0; 
   IntegerListElement current = first; 
   while(idx != i){ 
    current = current.next; 
    idx ++; 
   } 
   return current; 
  } 
  public int get(int i){ 
   return this.getElement(i).value; 
  } 
 public int add(int pos, int val){ 
   IntegerListElement newElem = new IntegerListElement(); 
   newElem.value = val; 
   if(pos > 0){ 
    IntegerListElement e = this.getElement(pos‐1); 
    newElem.next = e.next; 
    e.next = newElem; 
   }else{ 
    newElem.next = this.first; 
    this.first = newElem; 
   }

Suchen und Sortieren

Suchen und Sortieren sind voneinander abhängige Operationen. Dabei gibt es zwei Ansätze: Wenn Elemente nie sortiert sind, dann ist die Suche sehr aufwändig. Wenn die Elemente sortiert sind, wird die Suche erleichtert, jedoch kann das Sortieren an sich sehr aufwändig sein. Wenn Elemente hinzugefügt oder gelöscht werden ist diese Problematik noch sichtbarer. Nur ein unsortiertes Element macht die Suche aufwändig, doch bei jeder Einfügung oder Löschung zu sortieren ist ebenfalls sehr aufwändig. Spezielle dynamische Datenstrukturen erlauben eine automatische und effiziente Sortierung bei Einfügung oder Löschung.

Lineare Datenstruktur in Java

• Arrays:

int[] arr = new int[10];

arr[1] = 4;

• Listen:

List<Integer> myList = new LinkedList<Integer>();

myList.add(5);

• Neben LinkedList unterstützt Java eine Reihe weiterer Listenimplementierungen mit unterschiedlichen Vor- und Nachteilen
• Schnittstelle List<Type> beinhaltet die gemeinsamen Methoden

Suche

• Problembeschreibung

Die Eingabe ist eine Folge F mit n Elementen von Zahlen und Suchelementen k. Die Ausgabe ist eine erfolgreiche oder nicht erfolgreiche Suche. Erfolgreich ist sie, wenn der Index p $(0\leq p<n)$ ist. Eventuell muss man festlegen, was bei Mehrfachvorkommen passiert. Normalerweise gilt dann das erste Vorkommen. Ist die Suche nicht erfolgreich, dann ist die Ausgabe -1.

• Merkmale der Suche

Es gibt immer einen Suchschlüssel für Suchelemente, z.B. Zahlen. Außerdem ist eine Suche immer erfolgreich oder erfolglos. Die Suche basiert auf Vergleichsoperationen und die Daten sind zunächst als Feld, bzw. Array, oder Liste dargestellt.

Suchverfahren

In den nachfolgenden Kapiteln lernen Sie die sequentielle, binäre und Fibonacci Suche kennen.

Literatur

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 zu finden.

Lineare Suche

Dieses Kapitel handelt von der linearen oder 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

 
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

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 $\Theta (n)$.

Sequentielle Suche in Java

 
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

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.

Binäre Suche

Dieses Kapitel behandelt die binäre Suche. Wir stellen uns die Frage, wie die Suche effizienter werden könnte. Das Prinzip der binären Suche ist zuerst den mittleren Eintrag zu wählen und zu prüfen ob sich der gesuchte Wert in der linken oder rechten Hälfte der Liste befindet. Anschließend fährt man rekursiv mit der Hälfte fort, in der sich der Eintrag befindet. Voraussetzung für das binäre Suchverfahren ist, dass die Folge sortiert ist. Das Suchverfahren entspricht dem Entwurfsmuster von Divide-and-Conquer.

Beispiel

Rekursiver Algorithmus

int BinarySearch(int[] F, int k){  
  /*input: Folge F der Länge n, Schlüssel k */
  /*output: Position p */
   return  BinarySearchRec(F, k, 0, F.length-1); //initialer Aufruf
} 
int BinarySearchRec (int[] F, int k, int u, int o) {
  /* input: Folge F der Länge n, Schlüssel k,
        untere Schranke u, obere Schranke o */
  /* output: Position p */ 
 
 m = (u+o)/2;
 if  (F[m] ==  k) return m;
 if  ( u == o) return -1;
 if  (F[m] >  k) return BinarySearchRec(F,k,u,m-1);
 return BinarySearchRec(F,k,m+1,o); 
}

Aufwands Analyse

Das Terminierungs-Theorem besagt, dass der Algorithmus BinarySearch für jede endliche Eingabe F nach endlicher Zeit terminiert. In jedem Rekursionsschritt verkürzt sich die Länge des betrachteten Arrays F um mehr als die Hälfte. Nach endlichen vielen Schritten hat das Array nur noch ein Element und die Suche endet entweder erfolgreich oder erfolglos. Falls das Element vorher gefunden wird terminiert der Algorithmus schon früher.

Das Korrektheits-Theorem besagt, dass falls das Array F ein Element k enthält, gibt BinarySearch(F.k) den Index eines Vorkommens von k zurück. Ansonsten gibt BinarySearch (F,k) den Wert ‐1 zurück. Beweisen kann man das durch die verallgemeinerte Induktion nach der Länge n von F. n=1: Der erste Aufruf von BinarySearchRec ist BinarySearchRec(F,k,0,0) und somit m=0. Ist F[0]=k so wird 0 zurückgegeben, ansonsten ‐1 da 0=0. n>1: Der erste Aufruf von BinarySearchRec ist BinarySearchRec(F,k,0,n‐1) und somit m=(n‐1)/2. Ist F[m]=k, so wird m zurückgegeben. Ansonsten wird rekursiv auf F[0...m‐1] oder F[m+1...n] fortgefahren. Da die Folge sortiert ist, kann k nur in einem der beiden Teile vorhanden sein.

Da die Liste nach jedem Aufruf halbiert wird, haben wir nach dem ersten Teilen der Folge noch n/2 Elemente, nach dem zweiten Schritt n/4 Elemente, nach dem dritten Schritt n/8 Elemente... daher lässt sich allgemein sagen, dass in jedem i-ten Schritt maximal $n/2^{i}$ Elemente, das heißt $log_{2}n$ Vergleiche bei der Suche. Im besten Fall hat die Suche nur einen Vergleich, weil der Suchschlüssel genau in der Mitte liegt. Im schlechtesten Fall und im Durchschnitt für eine erfolgreiche und eine erfolglose Suche liegt die Anzahl der Vergleiche bei $log_{2}n$.

Rekursionsgleichung

Für die erfolglose Suche ergibt sich folgende Rekursionsgleichung.

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&falls~n=1\\T(n/2)&sonst\end{array}}\right.$

Das Auflösen von T(n) nach Induktion ergibt eine $T(n)=\Theta (log~n)$ Laufzeit für eine erfolglose, also Worst-Case, Suche.

Iterativer Algorithmus

int  BinarySearch(int[] F, int k) {
   /* input: Folge F der Länge n, Schlüssel k */ 
   /*  output: Position p  (0 ≤ p ≤ n-1)  */
 
   int u = 0;
   int o = F.length-1; 
   int m;
   while (u <= o) { 
       m = (u+o)/2;
       if  (F[m] ==  k)
           return m; 
       else
           if (k < F[m]) 
               o = m-1;
           else
               u = m+1; 
     
  }    
  return -1;
}

Der erste Teil des Algorithmus ist die Initialisierung. Die while Schleife, besagt, dass so lange wiederholt werden soll, bis die angegebenen Schranken erreicht sind. Die if Anweisung ist die Abbruchbedingung. Der letzte Teil des Algorithmus (else) passt die obere, bzw. untere Schranke an.

Vergleich der Suchverfahren

Verfahren / #Elemente	$10$	$10^{2}$	$10^{3}$	$10^{4}$
sequenziell (n/2)	$\approx 5$	$\approx 50$	$\approx 500$	$\approx 5000$
binär $log_{2}n$	$\approx 3,3$	$\approx 6,6$	$\approx 9,9$	$\approx 13,3$

Literatur

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.2 zu finden.