Suchen in Arrays

Es ist schon wieder ein paar Monate her, als wir hier im Blog ein paar einfache und auch ein paar sehr schnelle Algorithmen für das Sortieren von Datenmengen vorgestellt haben. Heute soll es dagegen um ein weiteres Problem gehen, auf das mancher Programmierer mit Sicherheit im Laufe der Zeit auch einmal stoßen wird: Das Suchen eines bestimmten Elements in einer Menge von Daten. Da dieses Problem jedoch in verschiedenen Datenstrukturen unterschiedlich gut oder schlecht gelöst werden kann, wollen wir uns heute auf Arrays beschränken.
Genauer gesagt, möchten wir an dieser Stelle aber auf umfangreiche Herleitungen, Analysen und Korrektheitsbeweise verzichten, sondern viel mehr die Prinzipien der einzelnen Algorithmen erläutern und ein paar Vor- und Nachteile präsentieren.
Nun aber genug um den heißen Brei herumgeredet. Fangen wir einfach mal an…

Lineare Suche
Den Anfang macht ein zugegebenermaßen relativ einfacher Versuch, ein Element in einem Array zu suchen: die lineare Suche. Die Idee dahinter ist recht schnell erklärt: Es wird lediglich der Array von vorn nach hinten durchlaufen und jedes einzelne Element überprüft. Somit wird, falls das gesuchte Element überhaupt im Array enthalten ist, dieses auch garantiert gefunden, unabhängig davon, welche Elemente an welcher Stelle stehen. In Pseudocode sieht dieser Algorithmus in etwa wie folgt aus:

LinearSearch(A[1..n], x):

for i := 1 to n do
     if A[i] == x then
          return i //Juhu! Gefunden!
     end
end
return -1 //Ach, schade! Nichts gefunden.

Sonderlich schnell ist dieser Algorithmus natürlich nicht. Im besten Falle wird zwar nur ein einziger Vergleich benötigt, um das Ergebnis zu finden, im schlechsten (und durchschnittlichen) Falle jedoch bis zu n Vergleiche, falls n die Anzahl der Array-Elemente ist.

Binäre Suche
Ein klein wenig komplizierter wird es nun mit dem folgenden Algorithmus: die binäre Suche. Hierfür wird zunächst jedoch vorausgesetzt, dass der zu durchsuchende Array bereits sortiert wurde. Dann wird einfach das mittlere Element des Arrays mit dem zu suchenden Element verglichen. Ist das gesuchte Element größer als das mittlere Element, so sucht man einfach in der Array-Hälfte weiter, in der die größeren Elemente enthalten sind (also vom mittleren Element bis zum letzten Element). Ist das gesuchte Element dagegen kleiner, wird entsprechend die andere Hälfte des Arrays weiterdurchsucht. Im nächsten Schritt wird nun also wieder mit der binären Suche durchsucht, bis letztendlich der zu durchsuchende Array nur noch aus einem Element besteht (oder eben das Element schon vorher gefunden wurde). Zusammengefasst in Pseudocode sieht das letztendlich wie folgt aus:

BinarySearch(A[l..r], x):

m := floor((l+r)/2) //berechne das mittlere Element
if A[m] = x then //Juhu! Gefunden!
     return m
else if l >= r then //Och, schade! Doch nicht.
     return -1
else if A[m] > x then //in Hälfte mit größeren Elementen suchen
     return BinarySearch(A[m+1..r], x)
else //in Hälfte mit kleineren Elementen suchen
     return BinarySearch(A[l..m-1], x)
end

Im schlechtesten (und durchschnittlichen) Fall benötigt dieser Algorithmus rund log(n) Vergleiche, wenn der Array n viele Elemente enthält. Dies ist vor allem bei größeren Arrays deutlich schneller als die lineare Suche. Der einzige wirkliche Nachteil wurde dagegen bereits genannt: Der Array muss bereits sortiert sein. Ist der zu durchsuchende Array dagegen unsortiert, ist die lineare Suche effizienter, da das zusätzliche Sortieren deutlich mehr Zeit in Anspruch nimmt, als die binäre Suche letztlich einspart.

Interpolationssuche
Ein wenig schneller ist die wohl eher unbekannte, modifizierte Variante der binären Suche: die Interpolationssuche. Hier wird erneut der Array in zwei Teile geteilt. Diese sind jedoch nicht zwingend gleich groß. Stattdessen wird anhand des Wertes des gesuchten Elements eine position geschätzt, an der das Element liegen könnte und der Array geteilt wird. Es wird also so ähnlich gesucht, wie es der normaldenkende Mensch mit dem Telefonbuch auch machen würde: Sucht man nach einer Person, deren Namen mit W beginnt, versucht man nicht am Anfang oder in der Mitte mit der Suche zu beginnen, sondern weiter am Ende des Telefonbuches. Wie dies letztendlich implementiert wird, kann im folgenden nachgelesen werden:

InterpolatedSearch(A[l..r], x):

//zunächst die Abbruchbedingung, um Division durch 0 zu vermeiden
if A[l] = A[r] and A[l] = x then //Juhu! Gefunden!
     return l
else if l = r then //Och, leider nichts gefunden!
     return -1
end

m := floor(l + (l-r)*(x-A[l])/(A[r]-A[l])) //Berechnung der geschätzten Position
if A[m] = x then //Juhu! Gefunden!
     return m
else if A[m] < x then //in Teil mit größeren Elementen suchen
     return InterpolatedSearch(A[m+1..r], x)
else //in Teil mit kleineren Elementen suchen
     return InterpolatedSearch(A[l..m-1], x)
end

Im durchschnittlichen Fall werden für die Suche mit diesem Algorithmus etwa log(log(n)) Vergleiche benötigt, falls n die Anzahl der Array-Elemente ist. Im schlechtesten Fall (das gesuchte Element ist das erste oder letzte Element des Arrays) werden dagegen bis zu n Vergleiche benötigt.
Anzumerken ist, dass dieser Algorithmus ebenfalls den Nachteil besitzt, dass der Array zunächst sortiert werden muss - andernfalls ist auch hier die lineare Suche die effektivste Variante.

Das soll es dann auch erst einmal wieder gewesen sein. Natürlich gibt es noch weitere Suchalgorithmen, die diverse Nachteile der oben genannten Algorithmen ausbessern. Diese sind in der Regel jedoch recht komplex und meist nicht von Bedeutung.
Eine spezielle Datenstruktur, die es erlaubt, im durchschnittlichen Falle mit konstanter Anzahl von Vergleichen zu suchen, möchten wir dann demnächst noch in einem Artikel "Suchen in Hashtabellen" vorstellen.
Sollten bereits zu den oben genannten Algorithmen Fragen bestehen, können diese gerne in den Kommentaren gestellt werden.