点击这里

插值搜索是二进制搜索的改进变体。 该搜索算法适用于所需值的探测位置。 为使此算法正常工作，数据收集应采用有序和均匀分布的形式。

它的运行时复杂性是log ₂ (log ₂ n) 。

用C实现 (Implementation in C)

#include<stdio.h>
#define MAX 10
// array of items on which linear search will be conducted. 
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int find(int data) {
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;      
   int index = -1;
   while(lo <= hi) {
      printf("\nComparison %d  \n" , comparisons ) ;
      printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
      printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);
      comparisons++;
      // probe the mid point 
      mid = lo + (((double)(hi - lo)/(list[hi] - list[lo])) * (data - list[lo]));
      printf("mid = %d\n",mid);
      // data found 
      if(list[mid] == data) {
         index = mid;
         break;
      } else {
         if(list[mid] < data) {
            // if data is larger, data is in upper half 
            lo = mid + 1;
         } else {
            // if data is smaller, data is in lower half 
            hi = mid - 1;
         }
      }               
   }
   printf("\nTotal comparisons made: %d", --comparisons);
   return index;
}
int main() {
   //find location of 33
   int location = find(33);
   // if element was found 
   if(location != -1)
      printf("\nElement found at location: %d" ,(location+1));
   else
      printf("Element not found.");
   return 0;
}

如果我们编译并运行上面的程序，它将产生以下结果 -

输出 (Output)

Comparison 1
lo : 0, list[0] = 10
hi : 9, list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7

您可以更改搜索值并执行程序进行测试。