插補(bǔ)方式有:直線插補(bǔ),圓弧插補(bǔ),拋物線插補(bǔ),樣條線插補(bǔ)等，我們這里用到的是直線插補(bǔ)。
直線插補(bǔ)(Llne Interpolation)這是車床上常用的一種插補(bǔ)方式，在此方式中，兩點(diǎn)間的插補(bǔ)沿著直線的點(diǎn)群來逼近，沿此直線控制刀具的運(yùn)動(dòng)。
對于一個(gè)有序數(shù)組，一般我們可以使用二分查找發(fā)查找某一個(gè)元素，這里介紹另一種方法，插補(bǔ)(Interpolation)搜尋法。和二分查找直接用中間的元素和要找的元素比較不一樣，該算法利用數(shù)據(jù)分布近似直線來做比例運(yùn)算，求得一個(gè)索引和要找的元素比較。
如果卻搜尋的資料分布平均的話，可以使用插補(bǔ)搜尋法來進(jìn)行搜尋，在搜尋的對象比較多時(shí)，插補(bǔ)搜尋法會(huì)比二分搜尋法來的快速。有的書上說插補(bǔ)查找算法比二分查找速度快，我在同一臺機(jī)器上使用百萬級數(shù)據(jù)測試發(fā)現(xiàn)，事實(shí)上并不是這樣。插補(bǔ)查找可能收斂的速度的確比二分快一些，但是它的運(yùn)算過程中用到了乘法和除法這些耗時(shí)的運(yùn)算，所以實(shí)際效果并沒有二分查找的速度快。
插補(bǔ)搜尋算法分析
插補(bǔ)搜尋法是以資料分布的近似直線來作比例運(yùn)算，以求出中間的索引并進(jìn)行資料比對，如果取出的值小于要尋找的值，則提高下界，如果取出的值大于要尋找的值，則降低下界，如此不斷的減少搜尋的范圍，所以其本原則與二分搜尋法是相同的，至于中間值的尋找是透過比例運(yùn)算，如下所示，其中K是指定要尋找的對象， 而m則是可能的索引值www.yztrans.com
假設(shè)數(shù)組為a,下屆為low,上屆為high,要找的元素的K，則求得中間值為m
在二分查找中,m = low + (high - low) /2;
在插補(bǔ)查找中,m = low + (high - low) * (K - a[low]) / (a[high] - a[low])。
插補(bǔ)搜尋算法實(shí)現(xiàn)(C/OC)
#define MAX 100
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
//主程序(C/OC)
int number[MAX] = {0};
int i, find;
srand(time(NULL)); //產(chǎn)生隨機(jī)數(shù)種子
for(i = 0; i < MAX; i++) { //產(chǎn)生隨機(jī)數(shù)組
number[i] = rand() % 100;
}
quicksort(number, 0, MAX-1); //快速排序，是數(shù)組變成有序的
printf("數(shù)列：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
find = 11; //被搜索的數(shù)字
if((i = intsrch(number, find)) >= 0) //調(diào)用插入排序法
printf("\n找到數(shù)字于索引 %d ", i);
else
printf("\n找不到指定數(shù)");
printf("\n");
//插補(bǔ)搜尋法
int intsrch(int number[], int find) {
int low, mid, upper;
low = 0;
upper = MAX - 1;
while(low <= upper) {
mid = (upper-low)*
(find-number[low])/(number[upper]-number[low])
+ low; //核心算法的實(shí)現(xiàn)
if(mid < low || mid > upper) //為找到，查詢結(jié)束
return -1;
if(find < number[mid])
upper = mid - 1;
else if(find > number[mid])
low = mid + 1;
else //查詢成功
return mid;
}
return -1;
}
//快速排序法
void quicksort(int number[], int left, int right) {
int i, j, k, s;
if(left < right) {
s = number[(left+right)/2]; //以中間值為基準(zhǔn)
i = left - 1;
j = right + 1;
while(1) {
while(number[++i] < s) ; // 向右找
while(number[--j] > s) ; // 向左找
if(i >= j)
break;
SWAP(number[i], number[j]);
}
quicksort(number, left, i-1); // 對左邊進(jìn)行遞回
quicksort(number, j+1, right); // 對右邊進(jìn)行遞回
}
}