TList and BinarySearch error

Question

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.

Answer 1

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.

Answer 2

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.