[Algorithmus] Binäre Suche für Zeichenketten

[Luckie]

Hat jemand von euch eine Idee, wie man eine binäre Suche für Zeichenketten realisieren könnte? Das Problem ist ja, dass man Zeichenketten ja nicht auf größer oder kleiner vergleichen kann - oder doch?

[Der.Kaktus]

Hallo Micha,

schau mal hier-->Binarysearch

[Luckie]

Äh, ja mir ist auch gerade eingefallen dass man die Vregleiochsoperatoren auch auf Strings anwenden kann. Hat sich also erledigt.

Aber irgendwas stimmt noch nicht:

Delphi-Quellcode:

function TBSearch.Search(SortedStrArray: TStrArray; s: String): Integer;
var
  left              : Integer;
  middle            : Integer;
  right             : Integer;
  found             : Boolean;
  index             : Integer;
begin
  found := False;
  index := -1;
  left := 0;
  right := Length(SortedStrArray);

  while (left <= right) and (not Found) do
  begin
    middle := left + ((right - left) div 2);
    if (SortedStrArray[middle] = s) then
    begin
      index := middle;
      Found := True;
    end;
    if (SortedStrArray[middle] > s) then
      right := middle - 1
    else
      left := middle + 1;
  end;

  result := index;
end;

Suche ich nach einer Zeichenkette, die nicht vorkommt, bekomme ich gleich beim ersten Vergleich

Delphi-Quellcode:

if (SortedStrArray[middle] = s) then

eine AccessViolation. Irgendwas stimmt da nicht.

[Der.Kaktus]

aender mal die Zeile um

Delphi-Quellcode:

 //middle := left + ((right - left) div 2); 
 middle := (left + right) div 2;

[Luckie]

Ändert nichts an der AV. middle hat auch einen gültigen Wert. Wie kann ein Vergleich eine ASV auslösen?

Zitat:

---------------------------
Benachrichtigung über Debugger-Exception
---------------------------
Im Projekt Project1.exe ist eine Exception der Klasse EAccessViolation aufgetreten. Meldung: 'Zugriffsverletzung bei Adresse 0040465B in Modul 'Project1.exe'. Lesen von Adresse 00000012'. Prozeß wurde angehalten. Mit Einzelne Anweisung oder Start fortsetzen.
---------------------------
OK Hilfe
---------------------------

[marabu]

Hallo Michael,

nimm dir ein Beispiel an der Methode TStringList.Find() - deren Implementierung ist best practise, da der Rückgabewert für Index bei Misserfolg die Stelle bezeichnet, an der die Einfügung vorzunehmen wäre.

Freundliche Grüße

[alzaimar]

Der Vergleich führt nicht zur Zugriffsverletzung, sondern der Versuch, auf das Element 'middle' zuzugreifen, welches dann vermutlich außerhalb des Bereiches ist. Ändere mal diese Zeilen;

Delphi-Quellcode:

left := 0;
right := Length(SortedStrArray);

in

Delphi-Quellcode:

left := Low (SortedStrArray);
right := High(SortedStrArray);

[Luckie]

Zitat:

Zitat von alzaimar

Delphi-Quellcode:

left := Low (SortedStrArray);
right := High(SortedStrArray);

Danke, das scheint es gewesen zu sein. Aber darüber muss ich noch mal nachdenken. ;)

@marabu: Hm, wäre eine Option, allerdings nutze ich den Rückgabewert schon, für die Position, wo das Element gefunden wurde und -1 entspricht "nicht gefunden".

[Der.Kaktus]

..so, nun iss der Code wie bei dem Link von "#2" ;-)

[Amateurprofi]

Michael,
vielleicht solltest du das noch etwas optimieren.

Delphi-Quellcode:

var  ...
     relationship : integer;
begin
   ...
   relationship := CompareStr(SortedStrArray[middle], s);
   if relationship < 0 then begin
      // SortedStrArray[middle] < s
   else if relationship=0 then begin
      // SortedStrArray[middle] = s
   else begin
      // SortedStrArray[middle] > s
   end;
   ...
end;

Warum :
Bei deiner Konstruktion vergleichst du in der While-Schleife die Strings (bis auf den letzten Durchlauf) immer zwei Mal.
So, wie oben dargestellt, vergleichst du die Strings immer nur ein Mal und prüfst danach einen Integerwert, was deutlich schneller geht.