/* ======================================== */
/*    程式實例: 9_7.c                       */
/*    插補搜索                              */
/* ======================================== */
#include <stdlib.h>
#define MAX  20                   /* 最大陣列容量         */

struct element                    /* 記錄結(jié)構(gòu)宣告         */
{
   int key;                       /* 搜索鍵值             */
};
typedef struct element record;    /* 結(jié)構(gòu)新型態(tài)           */
record data[MAX] = {              /* 結(jié)構(gòu)陣列宣告         */
       2,   5,   7,   9,  17,  21,  25,
      33,  46,  48,  51,  52,  63,  69,
      77,  78,  80,  89,  94,  99 };

/* ---------------------------------------- */
/*  插補搜索                                */
/* ---------------------------------------- */
int intersearch(int n,int key)
{
   if ( key < data[0].key || key > data[n-1].key )
      return -1;                  /* 沒有找到             */
   else
      return interfind(key,0,n-1);  /* 遞回呼叫         */
}

/* ---------------------------------------- */
/*  插補搜索遞回處理                        */
/* ---------------------------------------- */
int interfind(int key,int left,int right)
{
   int next_guess;                /* 下一個可能索引       */
   int offset;                    /* 索引位移             */
   int range;                     /* 鍵值范圍             */
   int index_range;               /* 索引范圍             */
   int temp;

   if ( data[left].key == key )   /* 找到了               */
      return left;
   else
      /* 沒有找到 */
      if ( left == right ||
           data[left].key == data[right].key )
         return -1;
      else
      {
         index_range = right - left;  /* 計算索引范圍     */
         /* 計算鍵值范圍 */
         range = data[right].key - data[left].key;
         offset = key - data[left].key;   /* 計算鍵值位移 */
         temp = ( offset * index_range )  / range;
         next_guess = left + temp;      /* 下一個可能索引 */
         if ( next_guess == left )      /* 己試過         */
            next_guess++;
         if ( key < data[next_guess].key )
            /* 左邊部分遞回呼叫插補搜索 */
            return interfind(key,left,next_guess - 1);
         else
            /* 右邊部分遞回呼叫插補搜索 */
            return interfind(key,next_guess,right);
      }
}

/* ---------------------------------------- */
/*  主程式: 在一個已排序的陣列, 接著輸入    */
/*  值用插補搜索來找值.                     */
/* ---------------------------------------- */
void main()
{
   int found;                     /* 是否找到變數(shù)         */
   int value;                     /* 搜索值的內(nèi)容         */

   while ( 1 )                    /* 主回路開始           */
   {
      printf("\n請輸入搜索值(0-100) ==> ");
      scanf("%d",&value);         /* 讀入搜索值           */
      if ( value != -1 )
      {
         found = intersearch(MAX,value);  /* 呼叫插補搜索 */
         if ( found != -1 )
            printf("找到搜索值:%d[%d]\n",value,found);
         else
            printf("沒有找到搜索值:%d\n",value);
      }
      else
         exit(1);                 /* 結(jié)束程式             */
   }
}