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))
VIDEO
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))
VIDEO
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).
Exponential Search (Runtime: O(log i))
Wir starten mit einer kleinen Such-Range und verdoppeln den Index des
Suchbereiches immer, wenn wir unser Zielelement nicht gefunden haben.
Wenn wir eine Range gefunden haben, in der unser Ziel enthalten sein
könnte, starten wir eine Binary Search in dieser Range.