Mega Code Archive
Search for an item in an array very quickly [binary search]
<![CDATA[
{
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
}
]]>