보간 검색(Interpolation Search)

사전식 검색이라고도 하며 찾고자 하는 데이터가 있음직한 부분을 검색하는 방법이다. 보간 방법에 따라 검색 효율성이 달라지며 키 값의 분포가 일정할 때 주로 사용되는 방법이다. 보간 검색은 이진 검색과 유사하나 리스트의 가운데를 분할하지 않고 불균등하게 검색할 위치를 선택한다. 이진 검색과 마찬가지로 보간 검색을 사용하려면 데이터를 미리 정렬해야 한다.

보간 검색에서 키 값을 찾는 공식은 아래와 같다.

 

C언어]

void Interpolation_Search(int Array[], int n, int key)

{

   //int Array[] : 검색될 값들이 정렬되어있는 배열 변수

   //int n : 검색될 값들이 들어 있는 방수 변수

   //int key : 실제 검색될 값이 있는 들어있는 변수

   int fd; //찾는 자료가 있는 지 여부를 결정하는 변수

   int l; //최소키 값 또는 시작키 값을 넣는 변수

   int h; //최대키 값을 넣는 변수

   int m; //key값과 비교할 킷값을 넣을 변수

 

   l=1; h=n;

   while(1)

   {

      m = l + (int)((double)(key - Array[l]) / (double)(Array[h] - Array[l]) * (h - l));

 

      if(m>h) m--;

      if(m<l || m>h)

      {

         fd=No;

         break;

      }

      else if(key==Array[m])

      {

         fd=Yes;

         break;

      }

      else if(key<Array[m])

         h=--m;

      else

         l=++m;

   }

 

   if(fd==2)

      printf("찾고자 하는 자료가 있습니다.\n");

   if(fd==1)

      printf("찾고자 하는 자료는 없습니다.\n");

}

 

Python]

def InPolsearch(list, x):

    idx0 = 0

    idxn = (len(list) - 1)

    found = False

 

    while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]:

        #중간 지점을 확인한다.

        mid = idx0 + int(((float(idxn - idx0) / (list[idxn] - list[idx0])) * (x - list[idx0])))

 

        #검색 대상과 중간 지점의 값을 비교한다.

        if list[mid] == x:

            found = True

            return found

 

        if list[mid] < x:

            idx0 = mid + 1

 

    return found

 

 

출처]

국립 국어원 : 보간 검색

실전! 초보가 최고가 되는 C : 보간 검색(p228)

프로그래머가 알아야 할 알고리즘 40 : 보간 검색(p092)

 

 

참고 문제]

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도