String in StringList suchen

[alzaimar]

Hi oki:
Zunächst mein Ansatz mit einem Beispiel: Die Liste besteht aus drei Zeilen 'ABC', 'DE','FGHI'.
Der String 'S' sieht so aus: 'ABCDEFGHI'.
Die Liste Z sieht so aus: (1,4,6)

Ich suche nach 'E'. Die Position ist 5, liegt also zwischen 4 und 6, ergo ist es die 2.Zeile.

Nun zu meiner Pos.5 Hier hatte ich den Mund etwas zu voll genommen, weil ich an Hash-Verfahren dachte, das wird hier nicht funktionieren. Ich kann mich aber mit einem Bucket- oder einem Lookup-Suchverfahren aus der Affäre ziehen.

Wir müssen das binärse Suchverfahren knacken: Das ist in log2(n) Schritten am Ziel, schon ziemlich fix... Hmmm... Wir brauchen ein Verfahren, das eine Position P auf einen Index i in Z schneller abbildet.

Sei p die gefundene Position des Suchstrings in S

1.Ansatz (Lookup)
Wir definierten ein Hilfsarray H der Länge 5 (so lang wie S): (1,1,2,2,3,3,3,3). Somit ist H[p] = Zeilennummer. Der Aufwand ist O(1), mithin optimal. Nachteil: Verbrät viel Speicher.

2.Ansatz (Bucket)
Wir teilen die möglichen Positionen durch F (F z.B. 3) und erstellen wieder ein Hilfsarray H mit H[p div F] = p, hier also (1,1,3).
Wenn wir eine Position gefunden haben (p), steht die Zeilennummer in H[p div F]? Leider nicht. Denn im Beispiel wird Position 4 in die 1.Zeile gemappt, in Wirklichkeit ist es jedoch in der nächsten Zeile. Wir wenden also binary Search auf die Teilliste H[p div 3], H[p div 3 + 1] an und fertig.

Der Aufwand ist O(log_2(F)), also schon besser.