delphi - 插值搜索

Question

如何在 Delphi 中实现通用插值搜索？我试过从 Wikipedia移植它。但是它返回错误的结果。

function Search(var A: TArray<Integer>; const Index, Count, Item: Integer): Integer;
var
  L, H, M: Integer;
begin
  L := Index;
  H := Count;
  Result := -1;
  while (A[L] <= Item) and (A[H] >= Item)  do
  begin
    M := L + ((Item - A[L]) * (H - L)) div (A[H] - A[L]);
    if A[M] < Item then
      L := M + 1
    else if A[M] > Item then
      H := M - 1
    else
      Exit(M);

    if A[L] = Item then
      Exit(L)
    else
      Exit(-1);
  end;
end;

var
  A: TArray<Integer>;
  I: Integer;
begin
  A := TArray<Integer>.Create(1, 2, 3, 4, 5, 7, 7, 7, 7);
  I := Search(A, 0, High(A), 5); // Returns -1;
  ReadLn;
end.

Answer 1

这段代码：

  if A[L] = Item then
      Exit(L)
    else
      Exit(-1);

应该在while循环体之外

Answer 2

完整的工作解决方案。大概可以进一步优化。即使有重复，它也能工作，它只会输出第一个索引，如果你使用类似LevenshteinDistance.

type
    TCompare<T> = reference to function(const L, R: T): Integer;
    TArrayManager<T> = record
        class function InterpolationSearch(var A: TArray<T>; const Index, Count: Integer; const Item: T; const Distance, Compare: TCompare<T>): Integer; static;
    end;

class function TArrayManager<T>.InterpolationSearch(var A: TArray<T>; const Index, Count: Integer; const Item: T; const Distance, Compare: TCompare<T>): Integer;
var
  L, H, M, C: integer;
begin
  L := Index;
  H := Count;
  Result := -1;
  while L <= H do
  begin
    if L = H then
      M := L
    else
    begin
      M := L + (Distance(Item, A[L]) * (H - L)) div Distance(A[H], A[L]);
      if M < L then
        M := L
      else if M > H then
        M := H;
    end;
    C := Compare(A[M], Item);
    if C < 0 then
      L := M + 1
    else
    begin
      H := M - 1;
      if C = 0 then
      Result := M;
    end;
  end;
end;