In kurzer Zeit nach bestimmten Daten zu suchen, gehört zu den wichtigsten Aufgaben vieler Programme. In der Informatik gibt es viele, gut analysierte Algorithmen dafür. Studien sagen aus, daß Rechner zu 25% ihrer CPU-Zeit mit Suchen und Sortieren von Daten beschäftigt sind. In der Regel soll dabei ein Array nach einem bestimmten Element durchsucht werden. Als wichtigste Vertreter der Suchalgorithmen seien neben der (trivialen und langsamsten) sequentiellen Suche nur die binäre Suche, die Interpolationssuche, Hashing (Scattered Storage) und für Suchen in Zeichenketten der A. nach Knuth-Morris-Pratt und der A. nach Boyer-Moore genannt.
Die wesentlichsten Einteilungskriterien sind analog zu denen der Sortierverfahren.
Die sequentielle oder lineare Suche ist die trivialste Suchfunktion überhaupt und kann auf einen ungeordnetes Array angewandt werden. Sie ist von der Komplexität n/2, da im Schnitt n/2 Elemente verglichen werden müssen, um ein bestimmtes Element zu finden. Daher empfiehlt sich die sequentielle Suche nur in Prototypen oder falls das zu durchsuchende Array sehr klein ist. Für schnellere Suchfunktionen sollte die sequentielle Suche durch ein anderes Verfahren ersetzt werden.
Beispiel für eine sequentielle Suche nach einem int-Datum in einem int-Array durch eine sequentielle Suchfunktion searchi, die als Parameter das zu durchsuchende Array a, dessen Anzahl an Elementen n und das gesuchte Element key übernimmt und die Position des gesuchten Elements zurückliefert, falls gefunden, anderenfalls -1:
#include <stdio.h>
#define ITEMCOUNT(a) (sizeof(a)/sizeof(a[0]))
int searchi(int a[], int n, int key)
{
int i;
for (i=0; i<n; i++)
if (a[i] == key) /* Vergleich */
return i; /* Gefunden */
return -1; /* Nicht gefunden */
}
void main()
{
int ai[10]={0,11,22,33,44,55,66,77,88,99};
/* Suchen nach dem Datum 33 und Ausgabe der Position */
printf("%d gefunden an Position %d\n", 33,
searchi(ai,ITEMCOUNT(ai),33));
}Aufgabe: Der Compiler, mit dem Sie gerade arbeiten, verwendet intern eine String-Suchfunktion, um im Quelltext die Schlüsselworte zu erkennen. Schreiben Sie eine sequentielle Suchfunktion searchs, die nach einem String in einem Array von Strings sucht [Lösung].
Aufgabe: Überlegen Sie, wie Sie in einem sortierten Array schneller nach einem bestimmten Element suchen können. Nehmen wir an, Sie suchen das Datum 33 in einem Array mit den Werten 0, 11, 22, 33, 44, 55, 66, 77, 88 und 99. Sie ermitteln den Wert des mittleren Element des Arrays (sog. Median), die 44 (oder 55) und vergleichen ihn mit dem gesuchten Datum. In welcher Teilhälfte des Arrays müssen Sie nur weitersuchen? Schreiben Sie eine Funktion, die nach dieser Methode einen int-Wert in einem int-Array sucht.
#include <stdio.h>
#define ITEMCOUNT(a) (sizeof(a)/sizeof(a[0]))
/* Vorbedingung: sortiertes Array */
int bsearchi(int a[], int n, int key)
{
int low=0, mid, high=n-1;
while (low <= high) {
mid = (low + high) / 2;
if (key < a[mid]) /* Vergleich */
high = mid - 1; /* Durchsuche linken Teil */
else if (key > a[mid])
low = mid + 1; /* Durchsuche rechten Teil */
else /* Gefunden */
return mid;
}
return -1; /* Nicht gefunden */
}
void main()
{
int ai[]={0,11,22,33,44,55,66,77,88,99};
printf("%d gefunden an Position %d\n", 33,
bsearchi(ai,ITEMCOUNT(ai),33));
}Aufgabe: Schreiben Sie eine binäre String-Suchfunktion bsearchs [Lösung].
Aufgabe: Entwickeln Sie eine binäre Suchfunktion bsearch, die mit Arrays jeglichen Datentyps zurechtkommt. Arbeiten Sie dazu mit frei definierbaren int-Funktionen, die sie als Parameter an bsearch übergeben und die von bsearch intern aufgerufen werden. Diese frei definierte Funktion muß -1 zurückliefern, falls der gesuchte Schlüssel kleiner als das Vergleichselement ist, 0 falls gleich, und +1 falls er größer ist [Lösung].