Bislang war das schnellste Such verfahren für sortierte Listen die Binärsuche. Der im folgenden vorgestellte Algorithmus mit der Bezeichnung „Sekantensuche“ weist unter bestimmten Bedingungen ein besseres Zeitverhalten als die Binärsuche auf.

Die Sekantensuche ist ein Suchverfahren, dessen Algorithmus sich von der Newtonschen Tangentenmethode ableitet. Die Newtonsche Tangentenmethode ist ein Näherungsverfahren der numerischen Mathematik, welche der Nullstellenbestimmung dient. Das Näherungsverfahren wird durch Einsetzen eines x-Wertes in die Näherungsformel (siehe Abb. 1) gestartet. Das Ergebnis dieser Berechnung wird dann wieder in die Formel eingesetzt. Dieser Vorgang wird solange wiederholt, bis die Nullstelle mit ausreichender Genauigkeit angenähert wurde (Zu beachten ist, daß die Tangentenmethode sich nur unter bestimmten

Voraussetzungen annähert. Die Konvergenzbedingungen sollen hier allerdings nicht behandelt werden, da die Sekantensuche davon unabhängig arbeitet.). Die geometrische Deutung (siehe Abb. 1) der Tangentenmethode ist dabei folgende: Nach Einsetzen des Startwertes (x,) in die Formel wird eine Tangente (t() an die Kurve f(x) im Punkt (x₁,f(x₁)) gelegt und der Schnittpunkt (x2) der Tangente mit der x-Achse bestimmt. Dieser Schnittpunkt (x2) geht als neuer Startwert in die Formel ein. Durch Wiederholung erhält man eine Folge von Näherungen (x-Werten) für die Nullstelle.

Herleitung der Sekantensuche

Die Berechnung der Tangente (bei der Newtonschen Tangentenmethode) macht es erforderlich, die Steigung der Funktion f(x) im gewünschten Punkt (Näherung) zu ermitteln. Dies geschieht durch die Bestimmung der ersten Ableitung (f’(x)) der Funktion f(x) in diesem Punkt.

Um die aufwendige Bestimmung der ersten Ableitung zu vermeiden, kann auch eine Sekante (Gerade durch zwei Punkte der Funktion) an die Funktion gelegt werden. Dies erfordert die Verwendung von jeweils zwei Punkten der Funktion bei jedem Näherungsschritt. Die Näherungsformel lautet dann wie folgt:

x_n+1 = (x_n-1*y_n - x_n*y_n-1 / (y_n - y_n-1)

wobei y_n=f(x_n) ist.

Diese Variante der Tangentenmethode heißt Sekantenmethode und erfordert zwei Startwerte (Die Sekantenmethode weist im Gegensatz zur Tangentenmethode lineare Konvergenz auf, während die Tangentenmethode quadratisch konvergiert.). Das dargestellte Suchverfahren - die Sekantensuche - leitet sich direkt von dieser Methode ab, enthält aber zusätzliche Elemente (Mitführung von Intervallgrenzen, Intervallhalbierung), um die Arbeit mit ganzen Zahlen zu ermöglichen.

Voraussetzungen der Sekantensuche

Damit die Sekantensuche anwendbar ist und schneller als die Binärsuche arbeitet, sind einige Voraussetzungen zu erfüllen (Die Binärsuche leitet sich im übrigen ebenfalls aus einem Verfahren der numerischen Mathematik ab, welches als Bisektion, Intervallhalbierung oder Intervallschachtelung bekannt ist. Auch dieses Verfahren dient der Nullstellenbestimmung durch ein Näherungsverfahren.):

1. Das Feld, in dem gesucht wird, muß sortiert sein.
2. Die Feldelemente müssen im Bereich der ganze Zahlen liegen und auf dem Rechner darstellbar sein (INTEGER).
3. Vor dem Suchbeginn müssen das erste und das letzte bzw. das kleinste und das größte Element des Feldes bekannt sein.
4. Die Verteilung der Feldwerte muß möglichst linear oder zumindest glatt sein.

Zu 1.:
Wie die Binärsuche ist auch die Sekantensuche nur auf sortierte Felder anwendbar. Die Art der Sortierung (aufsteigend oder absteigend) ist im Gegensatz zur Binärsuche ohne Belang. Das Feld darf gleichgroße Werte enthalten.

Zu 2.:
Die Sekantensuche ist nur in Zahlfeldern anwendbar, da im Unterschied zur Binärsuche nichtein qualitativer, sondern ein quantitativer Vergleich zwischen Vergleichswert und Suchwert vorgenommen wird. Das heißt, es muß möglich sein, die Differenz zwischen dem zu suchenden Wert und einem Wert des Feldes zu bestimmen.

Zu 3.:
Betrachtet man ein Feld mit Zahlenwerten als die Repräsentation einer ganzzahligen Funktionsdarstellung - wobei die Funktion aufgrund der Sortierung monoton steigend oder fallend ist -, so sind die Indizes des Feldes als Abschnittswerte der x-Achse und die Feldwerte zu den Indizes als Funktionswerte in Richtung der y-Achse zu sehen (siehe Abb. 2). Der Suchalgorithmus beginnt mit der Bestimmung des Schnittpunktes zwischen einer Parallelen zur x-Achse im Abstand des gesuchten Wertes und einer Geraden durch den ersten und den letzten Feldwert (siehe Abb. 3). Zur Bestimmung dieser Geraden müssen der erste und der letzte Feldwert bekannt sein und zu Beginn der Suche an die Suchfunktion übergeben werden. Genaueres dazu findet sich im Abschnitt „Die Arbeitsweise der Sekantensuche“.

Zu 4.:
Die Suchzeiten der Sekantensuche sind nur gut, wenn die Verteilung der Feldwert linerar oder zumindest glatt ist. Die Linearität der Feldwerte bestimmt man, indem man eine Gerade durch den ersten und den letzten Feldwert legt (Das Feld wird hier wieder als Repräsentant einer Funktionsdarstellung betrachtet). Die Verteilung der Feldwerte ist um so linearer je näher die Feldwerte an dieser Geraden liegen. (Die Verteilung errechnet sich aus der Summe der absoluten Differenzen zwischen Feldwert und Geradenordinate.) Bei einer nahezu ideal linearen Verteilung (Fast alle Feldwerte liegen auf der Geraden, siehe Abb. 4) werden alle Elemente des Feldes in genau einem Suchschritt gefunden, unabhängig von der Feldgröße. Ist die Linearität der Feldwerte schlecht, so sollten die Feldwerte zumindest eine glatte Kurve bilden (Abb. 5) und nicht verstreut liegen (Abb. 6), wenn die Sekantensuche brauchbare Suchzeiten garantieren soll.

Der Algorithmus

Listing 1 zeigt uns zunächst die iterative Formulierung. Formuliert man den Algorithmus rekursiv, so wird die Suchprozedur einige Zeilen kürzer. Die zusätzlichen Prozeduraufrufe (rekursiver Aufruf) können aufgrund der geringen Anzahl der Suchschritte (Aufrufe) vernachlässigt werden. In Listing 2 finden wir die rekursive Formulierung. Im Vergleich dazu die Binärsuche in Listing 3.

Die Bedeutung der Prozedurparameter:

u: Intervalluntergrenze
o: Intervallobergrenze
m: Mitte zwischen oberer und unterer Intervallgrenze (nur bei der Binärsuche)
ni: Neuer Index
ai: Alter Index
dx: Differenz der Indizes (x-Koordinaten)
dy: Differenz der Feldwerte (y-Koordinaten) (dx und dy werden nur bei der iterativen Sekantensuche verwendet)
w: Gesuchter Feldwert
f: Feld mit sortierten Werten

Formeln:

Diese Formel dient der Bestimmung des neuen Indexwertes aufgrund, einer Sekante die durch die beiden Vorgänger werte gelegt wurde.

Hier wird eine Intervallhalbierung durchgeführt. Der neue Index liegt in der Intervallmitte.

Die Arbeitsweise der Sekantensuche

Im folgenden wird die Arbeitsweise der rekursiven Prozedur beschrieben. Die iterative Variante arbeitet ähnlich. Die Prozedur wird mit sechs Parametern aufgerufen, wobei „u“ und „o“ das Intervall angeben, in dem gesucht werden soll. Die Variablen „ai“ und „ni“ müssen beim Prozeduraufruf mit den Intervallgrenzen belegt werden; die Reihenfolge ist dabei unerheblich. Der Parameter „dy“ gibt die Differenz zwischen dem größten (letzten) und dem kleinsten (ersten) Schlüsselwert wieder und der Parameter „w“ enthält den zu suchenden Wert. Das Feld „f“, in dem der Wert gesucht wird, sollte global vereinbart sein. Ebenso ist es günstig, den Index „ni“ global zu deklarieren, um nach Beendigung der Prozedur feststellen zu können, ob der gesuchte Wert gefunden wurde (f[ni]=w). Da es sich um eine restrekursive Prozedur handelt, ist es ohne weiteres möglich, alle Parameter global zu vereinbaren.

PROCEDURE sekantensuche(ai,dx,dy,w :INTEGER); VAR ni,u,o :INTEGER; BEGIN u:=ai; o:=ai+dx; REPEAT IF dy=0 THEN dy:=1; ni:=(w-f[ai])*(ni-ai) DIV dy +ai; IF (ni>o) OR (ni<u) THEN ni:=(o+u) DIV 2; IF w>f[ni] THEN u:=succ(ni) ELSE o:=pred(ni); dy:=f[ni]-f[ai]; dx:=ni-ai; ai:=ni UNTIL (o>u) OR (f[ni]=w) END;

Listing 1

Beispielaufruf:

• Werte im Feld f.
• Indexbereich von 1 bis 1000.
• Zu suchender Feldwert 100.

Iterative Variante:

Rekursive Variante:

Um den gesuchten Wert zu finden, wird in der Prozedur eine Gerade durch die Feldwerte f[ai] und f[ni] gelegt. Beim ersten Prozeduraufruf sind dies der erste und der letzte Feldwert. Dann wird der Schnittpunkt der Geraden mit einer Parallelen zur x-Achse im Abstand w (gesuchter Wert) bestimmt (siehe Abb. 2) und der Abszissenwert (x-Wert) dieses Schnittpunktes der Variablen „ni“ zugewiesen (Zeile 2). Diese Schnittpunktbestimmung macht es erforderlich, daß der Fall einer waagrechten Geraden (Parallele zur x-Achse, Steigung gleich Null) abgefangen wird (Zeile 1), denn ein Schnittpunkt zwischen zwei Parallelen kann nicht bestimmt werden. Wenn die Differenz der y-Koordinaten von Anfangspunkt und Endpunkt der Geraden Null beträgt (dy=0, f[ni]=f[ai], das Feld enthält gleiche Werte), so wird die Differenz auf den kleinst möglichen Wert (bei ganzen Zahlen ist dies die 1) gesetzt. Die Variable „ni“ enthält nach diesem 1. Suchschritt eine erste Schätzung für den Index des gesuchten Feldwertes w. Liegt diese Schätzung außerhalb der Intervallgrenzen (Vergleich in Zeile 3 des Such Verfahrens), so wird eine Intervallhalbierung durchgeführt und der mittlere Wert der Variablen „ni“ zugewiesen (Zeile 4). Sodann wird geprüft (Zeile 5), ob der Feldwert f[ni] zum berechneten Index dem gesuchten Wert entspricht (f[ni]=w) oder ob das Intervall die Größe Null hat (o>u, obere Intervallgrenze größer als die untere Intervallgrenze). Ist eine dieser Bedingungen erfüllt, bricht die Suche ab. Im anderen Fall erfolgt ein rekursiver Aufruf (Zeile 7 oder 8), welcher einen weiteren Suchschritt einleitet. Aufgrund der Bedingung w>f[ni] (Zeile 6) wird entschieden, mit welchen Parameterwerten der rekursive Aufruf erfolgt bzw. in welchem Teilintervall ((ni,o] (Zeile 7) oder [u,ni) (Zeile 8)) die Suche fortgesetzt wird. {(a,b] entspricht a>x<=b, [a,b) entspricht a>=x<b}. Durch die Mitführung der Intervallgrenzen wird garantiert, daß die Suchschritte konvergieren und das Verfahren bei o>u (bedeutet, daß der Wert nicht im Feld enthalten war) abbricht.

Die Herleitung der Formel (Zeile 2) erfolgt aus der Zweipunkteform der Geradengleichung:

Wobei x=ni, x0=ai und y0 bzw. y die den Indizes zugehörigen Feldwerte sind (y=f[ni], y0=f[ai]). Bestimmt werden soll der Schnittpunkt der Geraden y=m(x-x0)+y0 mit einer Parallelen zur x-Achse im Abstand w (y=w). Durch Gleichsetzung erhält man w=m(x-x0)+y0.

Ermittelt werden soll die Abszisse (Index) des Schnittpunktes. Folglich Auflösen der Gleichung nach x (entspricht dem neuen Index ni).

mkann ersetzt werden durch dy/dx, wobei dx die Differenz zweier Indizes und dy die Differenz der zugehörigen Schlüsselwerte darstellen.

Ersetzt man die Bezeichnungen und führt wegen der diskreten Werte eine Ganzzahldivision durch, so erhält man folgenden Pascalausdruck:

Diese Formel liefert eine Abschätzung für den Index des gesuchten Feldwertes unter Zuhilfenahme einer Sekante, die durch die Feldwerte von zwei vorhergehenden Schätzungen verläuft (Beim ersten Aufruf der Prozedur sind dies die Intervallgrenzen). Sind innerhalb dieser zwei vorhergehenden Abschätzungen die Feldwerte ideal verteilt, so ist der erste gefundene Index der für den gesuchten Schlüsselwert, d.h es ist nur ein Suchschritt erforderlich. Da es bei einer entsprechend flachen Sekante Vorkommen kann, daß der neue Index außerhalb des Indexbereiches liegt oder das Verfahren wegen der diskreten Werte nicht konvergiert, wird in der Prozedur überprüft (Zeile 3), ob der errechnete Index innerhalb der mitgeführten Indexgrenzen (u,o) liegt und eventuell eine Intervallhalbierung durchgeführt werden muß (Zeile 4). So kann die Konvergenz des Verfahrens garantiert werden, wobei im schlechtesten Fall „Feldgröße-2“ Schritte benötigt werden.

Listing 2

Listing 3

Zwei Ablaufbeispiele

Die folgenden Beispiele beziehen sich auf ein Feld mit den in Bild 7a angegebenen 10 Feldwerten Bild 7 zeigt die graphische Darstellung des Feldes.

Die Binärsuche benötigt insgesamt 29 Suchschritte, um jeden Wert des Feldes zu finden; die Sekantensuche 25. Sucht man mit der Sekantensuche den ersten oder den letzten Feldwert, so benötigt man hierfür erwartungsgemäß genau einen Suchschritt, da die erste Sekante durch diese beiden Punkte verläuft und diese Punkte vorab bekannt sein müssen, um die Sekante zu bestimmen. Jedoch werden auch alle anderen Punkte, die nahe genug an der Geraden liegen, mit einem Suchschritt gefunden, so beispielsweise die Werte 20 und 92.

1. Beispiel: Suche Schlüsselwert 20

1. Suchschritt:

Berechnung des neuen Indizes „ni“:

Werte eingesetzt:

2. Beispiel (siehe Abb. 8): Suche des Schlüsselwertes 64

1. Suchschritt:

• Sekante durch Feldwerte für Index 1 und 10
• Errechneter Index ist 6
• Zugehöriger Feld wert 79 (zu groß)
• obere Intervallgrenze wird auf 5 gesetzt
• rekursiver Aufruf

2. Suchschritt:

• Sekante durch Feldweite für Index 1 und 6
• Errechneter Index ist 5 (liegt innerhalb des Intervalles)r
• Zugehöriger Feldwert 71 (zu groß)
• obere Intervallgrenze wird auf 4 gesetzt
• rekursiver Aufruf

3. Suchschritt:

• Sekante durch Feldwerte für Index 5 und 6
• Errechneter Index ist 2 (liegt innerhalb des Intervalles)
• Zugehöriger Feldwert 20 (zu klein)
• untere Intervallgrenze wird auf 3 gesetzt
• rekursiver Aufruf

4. Suchschritt:

• Sekante durch Feldwerte für Index 2 und 5
• Errechneter Index ist 4 (liegt innerhalb des Intervalles)
• Zugehöriger Feld wert 64 (Wert gefunden)
• Prozedurende

⁶ Anzahl der Suchschritte, die die Sekantensuche benötigt, um den angegebenen Feldwert zu finden. ⁷ Anzahl der Suchschritte, die die Binärsuche benötigt. um den angegebenen Feldwert zu finden.

Tabelle 2

Die einzelnen Feldwerte der Liste wurden mit folgenden Schätzungen gefunden:

Tabelle 1

Wird die Entfernung der Feldwerte zur 1. Sekante groß, so sind mehrere Schätzungen (Sekantenberechnungen, Suchschritte) notwendig, um den Index zu finden. Die Anzahl der notwendigen Suchschritte wächst mit zunehmender Differenz (Sekante-Feldwert) an.

Binärsuche kontra Sekantensuche

Vergleicht man die Binärsuche mit der Sekantensuche, so erkennt man, daß ein Suchschritt der Sekantensuche rund doppelt so lange dauert wie ein Schritt der Binärsuche. Diesen Vorsprung der Binärsuche kann die Sekantensuche erst bei Feldern mit mehr als 1000 Elementen einholen. Findet die Suche allerdings nicht im Hauptspeicher sondern auf einem externen Speichermedium (Platte) statt, so sind noch die Blocktransferzeiten zu berücksichtigen. Hier sollte die Sekantensuche vorteilhaft arbeiten, da der erste Suchschritt zumeist schon im richtigen Block liegt und die Transferzeiten damit klein bleiben. Die Binärsuche sollte hier schlechter abschneiden, da die Suchschritte verstreuter liegen. Zudem überwiegen dann die Blocktransferzeiten die Suchschrittdauer im Hauptspeicher bei weitem, so daß sich die Gesamtzeiten für einen Suchschritt der Sekantensuche an die Zeiten der Binärsuche annähem. Da die Sekantensuche im Schnitt aber weniger Suchschritte benötigt, müßte sie schon bei kleineren Feldgrößen schneller als die Binärsuche werden. Das Zeitverhalten der Sekantensuche auf externen Speichermedien wurde allerdings bislang nicht getestet.Die folgende Tabelle gibt einen Vergleich zwischen Binärsuche und Sekantensuche wieder:

Zur Tabelle 2: Das Feld f[1..n] enthielt jeweils eine Folge von Zufallswerten im Bereich von 1-n. Sortiert wurde mit dem Sortieralgorithmus Quicksort. Alle Messung wurden auf einem Mega ST 2 mit ST PASCAL+ durchgeführt. Die Werte für die Suchzeiten und die Suchschritte wurden aus dem Mittel von jeweils drei Messungen gebildet. Die Suchzeiten geben an, wieviel Zeit benötigt wurde, um jedes Element des Feldes zu finden (also die Summe der einzelnen Suchzeiten). Die Anzahl der durchschnittlichen Suchschritte errechnet sich aus der Summe der Suchschritte zum Auffinden jedes Feldelementes dividiert durch die Feldgröße n. Wie zu sehen ist, steigt diese Zahl bei der Sekantensuche mit zunehmender Feldgröße an, wenn auch langsamer als bei der Binärsuche. Dies liegt an der zunehmenden Verschlechterung der Verteilung der Feldwerte mit steigender Listengröße. Trotzdem beginnt sich der Einsatz der Sekantensuche bei Feldern mit mehr als 1000 Elementen zu lohnen.

Der folgende Graph (Abb. 9) zeigt die Anzahl der durchschnittlichen Suchschritte in Abhängigkeit von der Feldgröße. Die Binärsuche stellt sich hier erwartungsgemäß (da Intervallhalbierung gilt : Suchschritte_max= log₂n+1 ) als logarithmische Kurve dar. Die Basis des dargestellten Logarithmus liegt aufgrund der Durchschnittsbildung etwas höher (die Kurve wird flacher) als 2, nämlich ca. bei 2.19.

Auch die Kurve der Sekantensuche zeigt sich bei dieser Verteilung (nicht ideal) als logarithmische Kurve mit einer Basis von ca. 15.65. Sind die Feld werte jedoch ideal verteilt, so bildet die Sekantensuche eine Parallele zur x-Achse im Abstand 1 (ein Suchschritt). Je besser die Verteilung ist, um so mehr nähert sich die logarithmische Kurve der Geraden an. Trägt man die Suchzeit in Abhängigkeit von der Feldgröße an (Abb. 10), so erkennt man, daß die Sekanntensuche mit zunehmender Feldgröße immer mehr Zeit im Vergleich zur Binärsuche einspart. Ist die Verteilung der Feldwert ideal, so wird jedes Element des Feldes in genau einem Suchschritt gefunden. Daraus folgt eine konstante Suchzeit, die sich in der Parallelen zur x-Achse im Abstand der Zeit für einen Suchschritt (ca. 0.44 ms) widerspiegelt. Ein Suchschritt der Binärsuche dauert ca. 0.22 ms. Es ergeben sich Geraden, weil nicht die durchschnittliche Suchzeit, sondern die Gesamtsuchzeit angetragen wurde.

Anwendungsbereiche der Sekantensuche

Die Anwendungen der Sekantensuche sind aufgrund der oben genannten Restriktionen auf Zahlenfelder beschränkt. Auch lohnt sich der Einsatz erst bei großen bis sehr großen Feldern. Wenn allerdings auf externen Speichermedien gesucht wird, können auch kleinere Felder schon vorteilhaftbearbeitet werden. Weiterhin sollten die Zahlenwerte der Felder eine gute Verteilung aufweisen; dies ist zumeist bei fortlaufenden Zahlenlisten wie Teilenummern, Rechnungsnummern, Statistiken usw. der Fall. Ist dies nicht der Fall, so nähert sich die Suchschrittzahl der Sekantensuche der Binärsuche. Zu beachten ist, daß aufgrund der Sekantenberechnung der Bereich der vom Rechner verarbeitbaren Zahlen eingehalten werden muß. Negativ wirkt sich hier die Multiplikation in der Formel zur Indexberechnung aus, welche bewirkt, daß folgende Bedingung gelten muß:

Daraus folgt, daß es sich empfiehlt Long-Integers zur Berechnung zu verwenden.

Fazit

• Die Sekantensuche ist nicht so allgemein einsetzbar wie die Binärsuche (Zahlenfelder, Verteilung der Feldwerte).
• Die maximal verarbeitbaren Listenlängen sind bei der Sekantensuche kleiner als bei der Binärsuche.
• Die Suchzeiten der Sekantensuche hängen zwar weniger von der Feldgröße, dafür aber mehr von den Feldwerten ab.
• Die Sekantensuche ist vorrangig für die Suche auf externen Speichermedien geeignet.
• Wenn die Verteilung der Feldwerte gut ist, ist die Sekantensuche ein sehr gutes Suchverfahren.

Literatur:

Bartsch, Hans-Jochen : Taschenbuch mathematischer Formeln; Verlag Harri Deutsch, Frankfurt 1986

Wirth, Niklaus : Algorithmen und Datenstrukturen; Teubner, Stuttgart 1983

Wollschlaeger, Peter: ATARI-ST-Programmierpraxis ST PASCAL; Markt-und-Technik-Verlag, Haar bei München 1987