TList和BinarySearch错误

Question

我对TList和BinarySearch有一些问题。我有这样的结构：

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

并声明：

var oDoubleEstr: TDoubleEstr;

然后，我使用这个函数正确地初始化列表：

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;

现在，我定义这个过程：

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

然后在我的主过程中：

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;

它把我变成了一个错误。从某种意义上说，索引为" index“元素与我键入的元素不对应。当然，oDoubleEstr的排序是正确的，但不知道我错在哪里。构造比较是这样定义的：

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

我认为这个错误是在构造中，但不能理解为解决它。通常，我希望检查元素是否存在，如果存在，则获取索引。作为元素，我的意思是在我的例子中只有一个字段是双精度的。我试着解释得更好，我的列表是如此之多：

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

如果我将元素设置为(89,90)，则应将我的值: 4004转换为索引，如果找到，则为true，否则为false。谢谢你的帮助。

Answer 1

我不确定您要做什么，但该Compare函数无效。比较函数需要具有以下对称属性：

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

您的函数没有此属性，因为您将Double[1]与Double[2]进行了比较。

您还可以在比较函数中使用减法来运行范围错误的风险。我会使用<和>运算符。

我不太愿意建议比较函数应该是什么，因为我不确定你想要的排序标准是什么。如果您想要按字典顺序进行比较(即按字母顺序排序)，则首先比较Double[1]值，如果它们比较相等，则对Double[2]值执行第二次比较。

但是，既然我已经再次研究了构建列表的方式，并且现在我看到您断言该列表是按结构排序的，那么order函数应该是什么就很清楚了。如下所示：

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;

请注意，我已经将compare函数的符号从您的原始版本中颠倒了过来，尽管它有缺陷。你的次要问题(参见对Ville答案的评论)是因为列表没有按照你用于搜索的相同顺序进行排序。您必须使用相同的比较进行排序和搜索。二分搜索算法就是以此为基础的。

顺便说一句，我认为Double是一个糟糕的变量名，因为它也是一个基本类型。使用PDoubleEstr来命名记录是非常混乱的，因为P前缀的传统用法是指针。

Answer 2

是的，大卫·赫弗曼是正确的。如果你这样定义你的比较函数，它将会工作：

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;

重要的一点是，您需要比较双精度数组中的两个值以获得匹配。