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; 

then在我的主要程序中：

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; 

它變成了一個錯誤。從某種意義上說，索引爲「索引」的元素不符合我輸入的元素。 當然，oDoubleEstr排序正確，不明白我的錯誤。 比較的結構是這樣定義的：

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 

如果我設置元素（89,90），它應該是把我作爲指標值：4004和真實，如發現或否則爲false。 感謝您的幫助。

Answer 1

我不確定你想要做什麼，但該Compare函數無效。比較功能需要具備以下對稱特性：

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

因爲你Double[2]比較Double[1]你的函數沒有這個屬性。

您還會在比較函數中使用減法運行範圍錯誤的風險。我會使用<和>運營商。

我很不情願地建議比較函數應該是什麼，因爲我不確定你想要的排序標準是什麼。如果要進行詞典對比（即按字母順序排列），則首先比較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前綴的常規用法是用於指針。

Answer 2

是David Hefferman是對的。如果你像這樣定義你的比較功能，將工作：

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; 

最重要的一點是，你需要兩個值雙數組中比較得到匹配。

Answer 3

我有一個位其他問題，以從上面的例子中，如果我有：

type 
    PDBDouble = record 
    Extract: array of Integer; 
    Count: Integer; 
    end; 
    TDBDouble = TList<PDBDouble>; 

我使陣列與動態大小爲n（0..N-1），並且我想比較n個元素數組的，我已經寫了：

function TArchive.Compare(const Left, Right: PDBDouble): Integer; 
begin 
    Result := CompareInt(Left.Extract[0], Right.Extract[0]); 
    if Result = 0 then 
    Result := CompareInt(Left.Extract[1], Right.Extract[1]); 
    if Result = 0 then 
    Result := CompareInt(Left.Extract[2], Right.Extract[2]); 
    if Result = 0 then 
    Result := CompareInt(Left.Extract[3], Right.Extract[3]); 
    ... 
    if Result = 0 then 
    Result := CompareInt(Left.Extract[n-1], Right.Extract[n-1]); 
end; 

使用二分查找，對於一些價值正返回正確的結果，當n的其他值不會返回正確的價值觀，我能解決這個問題？再次感謝。