Suchen

Suchen

Bei den meisten Zuordnungs- oder Übersetzungsproblemen muß gesucht werden.

Suchen eines Stichwortes in Lexikon oder Wörterbuch.

Ein PASCAL-Compiler sucht nach einem aus der Eingabedatei gelesenen Wort in einer Tabelle der reservierten Worte, um zu entscheiden, ob es ein reserviertes Wort ist.

Suchen einer Postleitzahl, um die zugehörige Stadt auszugeben.

In allen folgenden Suchalgorithmen wird vorausgesetzt, daß die zu durchsuchenden Daten in einem durch

TYPE suchfeld = ARRAY[1..max] OF integer

deklarierten ARRAY stehen. Der Parameter n in den folgenden Prozeduren gibt die Zahl der gültigen Einträge in dem ARRAY an.

Lineare Suche, Vergleich mit allen Daten; keine Voraussetzung an Daten. Laufzeit .

   FUNCTION find(key:integer; n: integer; a: 
   suchfeld):integer; 
   VAR i,k: integer; 
   BEGIN
      i:=0; k:=1; 
      WHILE (k<=n) AND (i=0) DO BEGIN   
         if key=a[k] THEN i:=k; 
         k:=k+1;  
  
      END;
      find:=i;
   END;

Bei erfolgreicher Suche wird der Index des gefundenen Elementes als Funktionswert zurückgeliefert, anderenfalls ist der Funktionswert Null.

Binäre Suche, erfordert sortierte Daten. Laufzeit . Durch fortgesetzte Halbierung des Suchintervalles wird die Suche auf immer weniger Elemente beschränkt, bis das Element gefunden ist.

 
    FUNCTION find(key: integer; n: integer; a:
    suchfeld): integer; 
    BEGIN
       anfang:=1; ende:=n; 
       i:=0; 
       REPEAT
          mitte:=(anfang+ende) DIV 2;  
          IF a[mitte]<key THEN ende:=mitte-1  
          ELSE IF a[mitte]>key THEN anfang:=mitte 
          ELSE i:=mitte;
       UNTIL (anfang=ende) or (i>0); 
       IF a[anfang]=key THEN i:=anfang; 
       find:=i;
    END;