Binäre Suche

[Luckie]

Delphi-Quellcode:

(*
 * Author  : Michael Puff - [url]http://www.michael-puff.de[/url]
 * Date    : 2008-06-03
 * License : PUBLIC DOMAIN
 *)

unit BSearch;

interface

type
  TIntArray = array of Integer;
  TStrArray = array of string;
  TBSearch = class(TObject)
  private
    procedure QuickSort(var Strings: TStrArray; Start, Stop: Integer); overload;
    procedure QuickSort(var IntArray: TIntArray; Start, Stop: Integer); overload;
  public
    function Search(IntArray: TIntArray; x: Integer; Sorted: Boolean): Integer; overload;
    function Search(StrArray: TStrArray; s: string; Sorted: Boolean): Integer; overload;
  end;

implementation

{ TBSearch }

////////////////////////////////////////////////////////////////////////////////
// Procedure : TBSearch.QuickSort
// Author    : Derek van Daal
// Date      : 2008-06-03
// Comment   : [url]http://www.swissdelphicenter.ch/torry/showcode.php?id=1916[/url]
//             Integer support: Michael Puff
procedure TBSearch.QuickSort(var IntArray: TIntArray; Start, Stop: Integer);
var
  Left: Integer;
  Right: Integer;
  Mid: Integer;
  Pivot: Integer;
  Temp: Integer;
begin
  Left  := Start;
  Right := Stop;
  Mid   := (Start + Stop) div 2;

  Pivot := IntArray[mid];
  repeat
    while IntArray[Left] < Pivot do Inc(Left);
    while Pivot < IntArray[Right] do Dec(Right);
    if Left <= Right then
    begin
      Temp           := IntArray[Left];
      IntArray[Left]  := IntArray[Right]; // Swops the two Strings
      IntArray[Right] := Temp;
      Inc(Left);
      Dec(Right);
    end;
  until Left > Right;

  if Start < Right then QuickSort(IntArray, Start, Right); // Uses
  if Left < Stop then QuickSort(IntArray, Left, Stop);     // Recursion
end;

////////////////////////////////////////////////////////////////////////////////
// Procedure : TBSearch.QuickSort
// Author    : Derek van Daal
// Date      :
// Comment   : [url]http://www.swissdelphicenter.ch/torry/showcode.php?id=1916[/url]
procedure TBSearch.QuickSort(var Strings: TStrArray; Start, Stop: Integer);
var
  Left: Integer;
  Right: Integer;
  Mid: Integer;
  Pivot: string;
  Temp: string;
begin
  Left  := Start;
  Right := Stop;
  Mid   := (Start + Stop) div 2;

  Pivot := Strings[mid];
  repeat
    while Strings[Left] < Pivot do Inc(Left);
    while Pivot < Strings[Right] do Dec(Right);
    if Left <= Right then
    begin
      Temp           := Strings[Left];
      Strings[Left]  := Strings[Right]; // Swops the two Strings
      Strings[Right] := Temp;
      Inc(Left);
      Dec(Right);
    end;
  until Left > Right;

  if Start < Right then QuickSort(Strings, Start, Right); // Uses
  if Left < Stop then QuickSort(Strings, Left, Stop);     // Recursion
end;

////////////////////////////////////////////////////////////////////////////////
// Procedure : TBSearch.Search
// Author    : Michael Puff
// Date      : 2008-06-03
// Comment   : Returns index of element or -1
function TBSearch.Search(IntArray: TIntArray; x: Integer; Sorted: Boolean): Integer;
var
  left              : Integer;
  middle            : Integer;
  right             : Integer;
  found             : Boolean;
  index             : Integer;
begin
  if not Sorted then
    QuickSort(IntArray, 0, High(IntArray));

  found := False;
  index := -1;
  left := Low (IntArray);
  right := High(IntArray);

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

  result := index;
end;

////////////////////////////////////////////////////////////////////////////////
// Procedure : TBSearch.Search
// Author    : Michael Puff
// Date      : 2008-06-03
// Comment   : returns index of element or -1
//           : case sensitive
function TBSearch.Search(StrArray: TStrArray; s: String; Sorted: Boolean): Integer;
var
  left              : Integer;
  middle            : Integer;
  right             : Integer;
  found             : Boolean;
  index             : Integer;
begin
  if not Sorted then
    QuickSort(StrArray, 0, High(StrArray));

  found := False;
  index := -1;
  left := Low (StrArray);
  right := High(StrArray);

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

  result := index;
end;

end.

Stichworte: binäre Suche, binary search, Binärsuche, suchen, dynamische Arrays