Interpolation Search

Question

How can I implement a Genric Interpolation Search in Delphi? I've tried porting it from Wikipedia. However it returns the wrong result.

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

Full working solution. Can probably optimized further. It works even if there are duplicates, it will just output the first index aswell it will work with strings if you use something like 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;