Home > Informatik > Stufe Q1 > 12. Suchverfahren

12.1 Lineare Suche

Überblick - Lineare Suche - Binäre Suche - Binäre Suchbäume - Index- u. Interpolationssuche

Wenn Sie die Übungen der Folge 11 (Vokabelliste) erfolgreich bearbeitet haben, sind Sie dem Prinzip der linearen Suche bereits begegnet. In einer Liste deutsch/englischer Vokabeln sollte ein deutscher Begriff gesucht werden, zum Beispiel "Hund", und dann sollte die englische Übersetzung, also "dog", ausgegeben werden. Die Vokabeln waren in dem Objekt-Array Vokabelliste nicht sortiert, sondern befanden sich in der Reihenfolge in dem Array, wie sie vom Benutzer eingegeben worden sind.

public String english(String pDeutsch)
{
   for (int i=0; i < anzahl; i++)  
   {
      String d = liste[i].gibDeutsch();
      if (pDeutsch.equals(d)) 
         return liste[i].gibEnglisch();
   }
   return "Begriff nicht gefunden!";
}

Die lineare Suche, die Sie implementiert hatten, fing also ganz vorne im Array an zu suchen.

Das Deutsch-Attribut der jeweils nächsten Vokabel wurde mit der get-Methode gibDeutsch() sondiert und in der lokalen Variable d gespeichert. Dann wurde d mit dem Parameter pDeutsch verglichen, dazu wurde die equals()-Methode des Objektes pDeutsch verwendet. Stimmten beide Strings überein, wurde die englische Übersetzung zurück geliefert, und mit dem return-Befehl wurde die gesamte Methode auch beendet.

Fand die Suche keine Übereinstimmung in dem Array, wurde der String "Begriff nicht gefunden" zurück geliefert, und die Methode wurde beendet.

Definition: Lineare Suche:

Man fängt beim ersten Element der linearen Datenstruktur an zu suchen und macht so lange weiter, bis man

  • entweder die gesuchten Daten gefunden hat oder
  • am Ende der Datenstruktur angekommen ist und nichts gefunden hat.

Achten Sie darauf, dass diese Definition keinerlei Implementationshinweise enthält, sondern nur den "reinen" Algorithmus beschreibt, der dann in jeder beliebigen Programmiersprache implementiert werden kann.

Übungen

Übung 12.1-1 (Heft, 6 Punkte*)

Ein Schüler hat einen Entwurf für eine Java-Methode erstellt, die in einem Objekt-Array CD[] nach einem bestimmten Begriff sucht. Falls die gesuchte CD gefunden wurde, soll der Titel der CD ausgegeben werden. Wurde die CD nicht gefunden, soll ein entsprechender Hinweis ausgegeben werden.

Hier das Flussdiagramm des Schülers für den linearen Suchalgorithmus:

Ein Entwurf für einen Algorithmus zur linearen Suche

Ein Flussdiagramm für eine lineare Suche

Analysieren Sie diesen Entwurf und beurteilen Sie, ob er funktionieren könnte. Falls Sie Fehler finden, verbessern Sie den Entwurf.

*Die hier angegebenen Punktzahlen sind nur ein grober Vorschlag für die Lehrperson, die eventuell Ihre Lösungen bewerten muss und soll den ungefähren Schwierigkeitsgrad der Übung wiedergeben. Selbstverständlich hängt die Art und Gewichtung der Bewertung von dem jeweiligen Lehrer ab. Dies gilt übrigens auch für die folgenden Aufgaben und Übungen.

Lösungshinweise...

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

 

public String englisch(String deutsch)

Kleine Denkaufgabe

Kommen wir noch einmal auf die Vokabelliste der Folge 11 zurück. Eine Schülerin hat die Methode englisch() programmiert, welche die Übersetzung für einen deutschen Begriff zurück liefern soll:

public void englisch(String deutsch)
{
   String d,e;

   for (int vok=0; vok < anzahl; vok++)
   {
      d = liste[vok].gibDeutsch();
      e = liste[vok].gibEnglisch(); 
      if (deutsch.equals(d)) 
         return e;
      else
         return "Wort nicht enthalten";
   }
}
Übung 12.1-2 (Heft, 4 Punkte)

Dummerweise sind der Schülerin bei der Implementation zwei gravierende Fehler unterlaufen. Finden und korrigieren Sie diese Fehler!

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

Systematische Untersuchung der linearen Suche

Bei der Analyse der verschiedenen Suchverfahren wäre es recht umständlich, wenn wir ständig in riesigen Bücher-, Zeitschriften- oder CD-Sammlungen wühlen müssten. Daher konstruieren wir uns ein sehr einfaches Modellsystem, das aus einem Array von lediglich 32 ganzen Zahlen besteht.

Vorgehen

Die lineare Suche demonstriert man aber am besten mit Hilfe eines unsortierten Arrays aus int-Zahlen.

Lineare Suche in einem Array aus 32 int-Zahlen

Die Abbildung zeigt eine Liste von Zufallszahlen mit Werten zwischen 1 und 32. Jede Zahl kommt genau ein Mal vor. Um die lineare Suche zu simulieren, suchen wir uns fünf beliebige Zahlen aus, zum Beispiel 17, 28, 24, 16 und 11. Dann wird nachgeschaut, an welcher Position diese Zahlen in der Liste vorkommen. Die 17 kommt an der Position 20 vor, also benötigt der lineare Algorithmus 20 Suchschritte, um diese Zahl zu finden. Ähnlich wird mit den anderen vier Zahlen verfahren.

Ergebnisse

Rechnet man die Suchschritte für alle fünf Zahlen zusammen und dividiert anschließend durch 5, so erhält man für unser Beispiel den Durchschnittswert 14,8. Da der Array 32 Zahlen umfasst, liegt die Vermutung nahe, dass man bei N Zahlen wohl ungefähr N/2 Suchschritte zum Finden einer beliebigen Zahl benötigt. Der Suchaufwand kann also durch die Funktion O(N) = N charakterisiert werden.

Wieso heißt es dann nicht O(N) = N/2 ?

Bei dieser O-Notation ist es üblich, "Kleinigkeiten" wie Faktoren, Konstanten etc. zu vernachlässigen. Für einen linearen Algorithmus ist es egal, ob der Zeitaufwand N, N/2 , N/2 + 17 oder N/4 ist, man sagt allgemein, der Zeitaufwand lässt sich durch eine Funktion O(N) = N charakterisieren.

Wäre der Zeitaufwand dagegen quadratisch von N abhängig, wie dies z.B. beim Bubblesort der Fall ist (wegen der zwei for-Schleifen), würde man sagen, der Zeitaufwand lässt sich durch eine Funktion O(N) = N2 charakterisieren. Allgemein spricht man hier von der O-Notation, die häufig eingesetzt wird, um das Zeitverhalten von Algorithmen zu beschreiben (für Experten: Siehe Landau-Symbole in der Wikipedia).

Im günstigsten Fall (best case) befindet sich die gesuchte Zahl ganz vorne in der Liste und man braucht nur 1 Suchschritt. Im ungünstigsten Fall (worst case) befindet sich die gesuchte Zahl an der letzten Stelle des Arrays und man benötigt N Suchschritte. Wenn die Zahl gar nicht in der Liste vorhanden ist, braucht man ebenfalls N Suchschritte. Dieser Fall, dass die Zahl nicht vorhanden ist, wurde in unserem einfachen Modellsystem mit den 32 int-Zahlen allerdings noch nicht berücksichtigt, insofern ist das Modellsystem noch nicht perfekt.

Übung 12.1-3 (Heft, 6 Punkte)

Perfektionieren Sie das obige Modellsystem.

Größe des Arrays: 32 Zahlen.

Wertebereich der Zufallszahlen: 1..100; jede Zahl kommt höchstens einmal vor.

Suchzahlen: Zehn zufällige Zahlen im Bereich 1..100; manche kommen im Array vor, manche auch nicht.

Berechnen Sie die durchschnittliche Suchzeit für diese zehn Zufallszahlen.

Lösungshinweise

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

Übung 12.1-4 (PC, 7 Punkte)

Schreiben Sie ein Java-Programm, das einen Array mit 100 zufällig ausgewählten int-Zahlen im Bereich zwischen 1 und 1000 erzeugt und in der Konsole anzeigt.

2 Punkte gibt es, wenn die Konsolenausgabe besonders übersichtlich gestaltet wurde, zum Beispiel mit Hilfe von Tabulatoren "\t" zwischen den einzelnen Zahlen und genau 10 Zahlen pro Zeile.

3 Punkte gibt es, wenn jede Zufallszahl nur einmal in dem Array vorkommt.

2 Punkte gibt es dann für den Rest der Aufgabe: Statten Sie Ihr Programm dann mit einer Methode aus, die eine Suchzahl als int-Parameter annimmt und als int-Suchergebnis den Index der Zahl im Array ausgibt. So könnte die Signatur (der Kopf) dieser sondierenden Methode aussehen:

public int gibIndex(int suchzahl)

Sollte die Suchzahl nicht im Array vorkommen, soll der Wert 100 ausgegeben werden, da ja auch 100 Vergleiche benötigt wurden, um festzustellen, dass die Zahl nicht im Array vorhanden ist.

Lösungshinweise

Lösungsvorschlag auf den Seiten für Lehrer(innen)

Übung 12.1-5 (PC, 3 Punkte)

Erweitern Sie das Programm aus Übung 12.1-4 folgendermaßen:

Es sollen die Suchzeiten für 100 zufällige Suchzahlen ermittelt werden. Aus diesen 100 Suchzeiten soll dann die durchschnittliche Suchzeit berechnet werden. Die Suchzahlen sollen im Bereich zwischen 1 und 1000 liegen, also im gleichen Wertebereich wie die Zahlen des Arrays.

Lösungshinweise und Lösungen für diese einfache Ergänzungsaufgabe gibt es nicht.

Heben Sie den Quelltext gut auf, den Sie zum Lösen der Übung 12.1-5 erstellt haben. Sie können Teile des Quelltextes für die Übungen der Folge 12.2 gut gebrauchen!

Seitenanfang -
Weiter mit der binären Suche...