delphi - 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 排序正确，但不明白我错在哪里。构造 Compare 的定义如下:

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

我认为错误是在构造中，但不理解为解决它。一般来说，我想检查元素是否存在，如果存在则获取索引。作为元素，我的意思是在我的例子中只有字段 Double 。我尝试更好地解释，我的列表是如此丰富:

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

如果我将 Element 设置为 (89,90)，它应该将我作为索引值:4004，如果找到它，则为 true，否则为 false。感谢您的帮助。

Answer 1

我不确定你想做什么，但是 Compare功能无效。比较函数需要具有以下对称性:

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

您的函数没有此属性，因为您比较 Double[1]与 Double[2] .

比较函数中的减法还存在出现范围错误的风险。我会使用 <和>改为运营商。

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

但是，既然我再次查看了构建列表的方式，并且现在我看到您断言此列表在构建时已排序，那么顺序函数应该是什么就很清楚了。像这样的事情:

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;

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

<小时/>

顺便说一句，我认为 Double是一个糟糕的变量名，因为它也是一个基本类型。使用PDoubleEstr命名一条记录非常令人困惑，因为常规用法为 P前缀用于指针。