...search for an item in an array very quickly (Binary Search)?

{
Ever wondered if there is a quicker way to search for an item in a large array?
Sometimes you have to search for an item in an array that has thousands of
items - and what if the item you are looking for is the last one...

Here is a super fast way of doing it called BINARY SEARCHING.

Binary searching is a search method of dividing the list of possibilities
in two each time the loop is executed. The item in the middle of the
new set of possibilities is then compared with the searched item. If it isn't
a match, the loop is executed again until there is at least only one
possibility left or the item is not found.
The only setback of binary searching is that the list of items needs to
be sorted first.

Here is an example to quicksort the Strings and performed a binary search
on an array of String.
}

type
  TStringArray = array of string;

  {--------------------------------------------------------------------}
  //Start is the index of the first item of the array - usually 0
  //Stop is the index of the last item of the array
procedure QuickSort(var Strings: TStringArray; 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;
{--------------------------------------------------------------------}

function BinSearch(Strings: TStringArray; SubStr: string): Integer;
var
  First: Integer;
  Last: Integer;
  Pivot: Integer;
  Found: Boolean;
begin
  First  := Low(Strings); //Sets the first item of the range
  Last   := High(Strings); //Sets the last item of the range
  Found  := False; //Initializes the Found flag (Not found yet)
  Result := -1; //Initializes the Result

  //If First > Last then the searched item doesn't exist
  //If the item is found the loop will stop
  while (First <= Last) and (not Found) do
  begin
    //Gets the middle of the selected range
    Pivot := (First + Last) div 2;
    //Compares the String in the middle with the searched one
    if Strings[Pivot] = SubStr then
    begin
      Found  := True;
      Result := Pivot;
    end
    //If the Item in the middle has a bigger value than
    //the searched item, then select the first half
    else if Strings[Pivot] > SubStr then
      Last := Pivot - 1
        //else select the second half
    else 
      First := Pivot + 1;
  end;
end;
{--------------------------------------------------------------------}

//To use the Binary Search:
procedure Button1Click(Sender: TObject);
var
  MyStrings: TStringArray;
begin
  //Give some values to your strings and remember to
  //Set it to the correct length :)
  //..
  //..
  //..

  QuickSort(MyStrings, 0, High(MyStrings);
    ShowMessage('The index of 'Derek' is: ' +
    IntToStr(BinSearch(MyStrings, 'Derek')
    //If 'Derek' is in MyStrings, its index value will be returned,
    //otherwise -1 will be returned.
  end;

{
INTERESTING FACT:
A binary search on array of 1 000 000 items will execute the
loop AT MOST 20 times - no really. Here is how the possibilities
are eliminated:

1000000 div 2 =
500000 div 2 =
250000 div 2 =
125000 div 2 =
62500 div 2 =
31250 div 2 =
15625 div 2 =
7812 div 2 =
3906 div 2 =
1953 div 2 =
976 div 2 =
488 div 2 =
244 div 2 =
122 div 2 =
61 div 2 =
30 div 2 =
15 div 2 =
7 div 2 =
3 div 2 =
1

This is why its called BINARY SEARCH. Hope you are amazed ;-)

Regards
}

printed from
www.swissdelphicenter.ch
developers knowledge base