안녕하세요 만해입니다.

델코에 가니깐 쓸만한 검색 함수라고 있어서요

저도 테스팅 잠시 해봤는데요

괘않은것 같네요

int 만건의 정렬된 배열에서 1만번의 검색을 수행 시키는데 걸린 시간이 약

1초 조금 못 되네요

이정도면 빠른건가요?

소스는 이렇게 됩니다.

int __fastcall InterpolationSearch(int target, const int* List,int min, int max)
{
  int middle;
  while (min <= max)// do
  {
    if (List[min] == List[max])
    {
      if (List[min] == target)
        return min;
      else
        return 0;
    }
    middle = min + ((target - List[min]) * ((max - min) / (List[max] - List[min])));
    if ((middle < min) || (middle > max))
      return 0;
    if (target == List[middle])
      return middle;
    else if (target < List[middle])
      max = middle -1;
    else
      min = middle +1;
  }
   return 0;
}

파스칼의 경우 배열의 인자를 임의로 정할수 있지만

씨플플은 그렇지 않죠~

min변수는 무조건 0이 되고요

max 변수는 배열의 크기를 입력 하면 됩니다.

그리고 target은 찾고자 하는 값이고요

혹시나 제가 포팅을 잘못한건지도 몰라서 파스칼 소스도 같이 올립니다. 참고 하세요

function InterpolationSearch(target: Integer; List: PLongArray; min, 
  max: Integer): Longint; 
var 
  middle : Longint; 
begin 
  while min <= max do 
  begin 
    if List^[min] = List^[max] then 
    begin 
      if List^[min] = target then 
        Result := min 
      else 
        Result := 0; 
      exit; 
    end; 
    middle := 
      Round(min + ((target - List^[min]) * ((max - min) / (List^[max] - List^[min])))); 
    if (middle < min) OR (middle > max) then 
    begin 
      Result := 0; 
      exit; 
    end; 
    if target = List^[middle] then 
    begin 
      Result := middle; 
      exit; 
    end 
    else if target < List^[middle] then 
      max := middle -1 
    else 
      min := middle +1; 
  end; 
  Result := 0; 
end; 

즐프하세요~