3

i having some problem with TList and BinarySearch. I have this structure:

  PDoubleEstr = record
    Double: array [1..2] of Integer;
    Count: Integer;
  end;
  TDoubleEstr = TList<PDoubleEstr>;

and declare:

var oDoubleEstr: TDoubleEstr;

Then, i Initialize the list correctly using this function:

procedure Initialize;
var
  iIndex1, iIndex2: Integer;
  rDoubleEstr: PDoubleEstr;
begin
  oDoubleEstr.Clear;
  for iIndex1 := 1 to 89 do
    for iIndex2 := Succ(iIndex1) to 90 do
    begin
      with rDoubleEstr do
      begin
        Double[1] := iIndex1;
        Double[2] := iIndex2;
        Count := 0;
      end;
      oDoubleEstr.Add(rDoubleEstr);
    end;
end;

Now, i define this procedure:

procedure Element(const First: Integer; const Second: Integer; var Value: PDoubleEstr);
begin
  with Value do
  begin
    Double[1] := First;
    Double[2] := Second;
  end; 
end;

then in my main procedure:

procedure Main;
var 
  Value: PDoubleEstr;
  Index: Integer;
  flag: boolean;
begin
  Element(89, 90, Value);
  flag := oDoubleEstr.BinarySearch(Value, Index, TDelegatedComparer<PDoubleEstr>.Construct(Compare));
  Writeln(Flag:5, oDoubleEstr[Index].Double[1]:5, oDoubleEstr[Index].Double[2]:5);  
end;

It turn me an error. In sense that elements with index "Index" not correspond to element that i have typed. Of course, oDoubleEstr is sorted correctly, and not understand where i mistake. The construct Compare is so defined:

function TDouble.Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := Sign(Left.Double[1] - Right.Double[2]);
end;

and i think that error is in construct, but not understood as solve it. In general i want check if element exist, and if exist get the index. As element i mean only field Double in my case. I try to explain better, my list is so populate:

 1   2    // element 0
 1   3    
......
 1  90    
......
88  89
88  90
89  90    // element 4004

if i set Element as (89,90) it should be turn me as index the value: 4004 and true if found it or false otherwise. Thanks for help.

Improve this question

2 Answers 2

Reset to default
2

I'm not sure what you are trying to do, but that Compare function is not valid. A Compare function needs to have the following symmetry property:

Compare(a, b) = -Compare(b, a)

Your function does not have this property because you compare Double[1] with Double[2].

You also run the risk of a range error with the subtraction in your compare function. I would use < and > operators instead.

I am al ittle reluctant to suggest what the compare function should be because I'm not sure what your desired ordering criterion is. If you want a lexicographic comparison (i.e. an alphabetical ordering) then compare the Double[1] values first and if they compare equal, perform a second compare of the Double[2] values.

However, now that I have looked again at the way in which you build the list, and now that I see that you assert this list is sorted on construction, it is clear what the order function should be. Something like this:

function CompareInt(const Left, Right: Integer): Integer;
begin
  if Left<Right then begin
    Result := -1
  else if Left>Right then
    Result := 1
  else
    Result := 0;
end;

function Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := CompareInt(Left.Double[1], Right.Double[1]);
  if Result=0 then
    Result := CompareInt(Left.Double[2], Right.Double[2]);
end;

Note that I have reversed the sign of the compare function from your original, albeit flawed, version. Your secondary problems (see comments to Ville's answer) are because the the list is not be sorted according to the same ordering as you use for the search. You must sort and search with same compare. The binary search algorithm is predicated on this.

As an aside I think that Double is a poor variable name because it is also a fundamental type. The use of PDoubleEstr to name a record is very confusing because the conventional use for the P prefix is for a pointer.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Uhm as i should write it? I want simply to find in my list Element "Double" only that contain two number, and check if it exist or not exist and if exist in what position (index) it is. I have tried to study this solution looking some example. Can you give me more detail? Thanks again very much.
If you want to compare and search based on both values in the Double[] array, then use the function offered by Ville. However, that still is subject to overflow errors if your values are large enough. I doubt that's the case but I point it out for completeness.
@Marcello Right, I think I have got to the bottom of this now. See update. Binary search will only work if the list is ordered as determined by the compare function you provide.
1

Yes David Hefferman is correct. If you define your compare function like this it will work:

function Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := Sign(Left.Double[1] - Right.Double[1]);
  if Result=0 then
    Result := Sign(Left.Double[2] - Right.Double[2]);
end;

The important bit is that you need to compare both values in the double array to get a match.

Improve this answer

4 Comments

Hello i have tried to do so, but not read correct value, just it result as "random".
I trust you are sorting with this compare function also? You must sort and search with same compare.
Not understood sorry :( I use Compare only for research, the list is ordered correctly when i initialize it calling procedure: Initialize. To me interest only to check if field Double (defined as: array [1..2] of integer) exist in my list oDoubleEstr. I think to mistake to use the comparer. I am little confused.
I've looked at this again in more detail. The problem with the compare function in this answer is it does not match the order in which the list is constructed. The order in this answer is descending but the list is ascending. As I stated above the sort and search must use the same order.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.