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

 26 Visitors Online

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

 Tip Rating (99):     {
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 