whats new ¦  programming tips ¦  indy articles ¦  intraweb articles ¦  informations ¦  links ¦  interviews
 misc ¦  tutorials ¦  Add&Win Game

Tips (1548)

Database (90)
Files (137)
Forms (107)
Graphic (116)
IDE (21)
Indy (5)
Internet / LAN (131)
IntraWeb (0)
Math (76)
Misc (127)
Multimedia (45)
Objects/
ActiveX (51)

OpenTools API (3)
Printing (35)
Strings (83)
System (268)
VCL (243)

Top15

Tips sort by
component


Search Tip

Add new Tip

Add&Win Game

Advertising

23 Visitors Online


 
...search for an item in an array very quickly (Binary Search)?
Autor: Derek van Daal
[ Print tip ]  

Tip Rating (92):  
     


{
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
}


 

Rate this tip:

poor
very good


Copyright © by SwissDelphiCenter.ch
All trademarks are the sole property of their respective owners