Mega Code Archive
Binary search in a dataset
<![CDATA[
Title: Binary search in a dataset
Question: How to realize a binary search inside a dataset ?
Answer:
TQuery has no search functions like TTable's FindKey or GotoKey. Therefore you often find procedures in delphi projects that look like this:
function SeqSearch(AQuery:TQuery;AField,AValue:String): Boolean;
begin
with AQuery do begin
First;
while (not Eof) and
(not (FieldByName(AField).AsString = AValue)) do
Next;
Result := not Eof;
end;
end;
This is a sequential search - in the worst case this function would step trough the dataset until its end. It would take the maximum of time.
With the help of the moveby method its possible to implement a much better search algorithm - binary search:
function BinSearch(AQuery: TQuery; AField, AValue: String): Boolean;
var
Hi, Lo: Integer;
begin
with AQuery do begin
First;
Hi := RecordCount;
Lo := 0;
MoveBy(RecordCount div 2);
while (Hi - Lo) 1 do begin
if (FieldByName(AField).AsString AValue) then begin
Hi := Hi - ((Hi - Lo) div 2);
MoveBy(((Hi - Lo) div 2) * -1);
end
else begin
Lo := Lo + ((Hi - Lo) div 2);
MoveBy((Hi - Lo) div 2);
end;
end;
if (FieldByName(AField).AsString AValue) then Prior;
Result := (FieldByName(AField).AsString = AValue)
end;
end;
The only condition within this function is of course that the records are sorted ! This is realized easily through the 'ORDER BY' statement of the sql query.
The different is enormous !
The most important aspect is that the time of search is poorly corresponding with the amount of records in the dataset. To make this function complete a bookmark (TBookmark) is missing that would help to leave the dataset in the same state as before the search.
With the following sql statement
select * from customer
order by Company
(Databasename of TQuery is net to 'DBDEMOS') and the call of
SeqSearch(Query1,'Company',' Kirk Enterprises');
- 28 steps where necessary. With
BinSearch(Query1,'Company',' Kirk Enterprises');
the db-cursor is set to the right position after 8 steps !
]]>