Was sind Searching Algorithms?

Wir verwenden Suchalgorithmen, um ein Element mit bestimmten Eigenschaften aus einer Sammlung von Elementen zu finden. Ein Element kann dabei alles sein, von einem gespeicherten Datensatz oder einem Array-Element bis hin zu Elementen anderer Suchbereiche. Beispielsweise die Google Suche oder aber auch das Auffinden der Telefonnummer einer Freundin in einer langen Kontaktliste, kann mithilfe von Suchalgorithmen erleichtert werden. Es gibt verschiedene Suchalgorithmen. Auf einige von ihnen wird im folgenden eingegangen.

Linear Search (Space: O (1) Runtime: O(n))



Wir iterieren über eine Eingabe und vergleichen sie für jedes Element mit dem Zielelement. Wenn das aktuelle Element und das Ziel gleich sind, ist die Suche abgeschlossen. Diese Suche ist etwas ineffizient, da die gesamte Eingabe gescannt wird. O(n) (lineare) Zeitkomplexität, O(1) Raum.

Binary Search (Space: O (1) Runtime: O(log n))



Funktioniert nur bei sortierten Eingaben. Es ist ein Divide- & Conquer-Algorithmus. Sie funktioniert, indem der Mittelpunkt einer Eingabe ermittelt und das mittlere Element mit dem Zielelement verglichen wird. Wenn das mittlere Element unserem Zielelement entspricht, ist die Suche beendet. Wenn das Zielelement kleiner als das mittlere Element ist, durchsuchen wir die linke Hälfte der Eingabe (und wiederholen den Vorgang des Findens der Mitte und des Vergleichs). Wenn das Zielelement größer als das mittlere Element ist, durchsuchen wir die rechte Hälfte der Eingabe (und wiederholen...). Die binäre Suche reduziert die Zeitkomplexität auf O(log n) (logarithmisch) - da wir nicht die gesamte Eingabe scannen müssen (wie bei der linearen Suche). Space ist O(1).

Jump Search ((O(√ n))

Anstatt Element für Element zu prüfen, sucht dieser Algorithmus Block für Block, sodass weniger Elemente überprüft werden müssen.
Wir beginnen mit der Definition einer Blockgröße. Beginnend am Anfang der Liste überprüfen wir das letzte Element eines jeden Blocks. Ist das Element kleiner als der gesuchte Wert, springen wir zum nächsten Block. Wenn jedoch das letzte Element des aktuellen Blocks größer als der gesuchte Wert ist, führen wir eine lineare Suche in diesem Block durch. Die Komplexität der Sprungsuchzeit beträgt im schlimmsten Fall O(√ n).