插入查找

按比例查找的二分查找 插值公式如下 拿数位板玩玩 ---C语言实现 #include<stdio.h> #include<stdlib.h> #define RETURN_FAIL -1 //二分查找（折半查找）的优化 -> //-> 插值查找 int InterpolationSearch(int *Src_int,int Src_len,int SearchNum) { int LowIndex; int HighIndex; int MidIndex; if(Src_int == NULL || Src_len <= 0)return RETURN_FAIL; LowIndex = 1; HighIndex = Src_len; while(LowIndex <= HighIndex) { //按照比例插值 MidIndex = LowIndex+(SearchNum-Src_int[LowIndex])/(Src_int[HighIndex]-Src_int[LowIndex])*(HighIndex-LowIndex); if(Src_int[MidIndex] == SearchNum) { return MidIndex; } else if(Src_int[MidIndex] > SearchNum) { HighIndex = MidIndex-1; } else { LowIndex = MidIndex+1; } } return RETURN_FAIL; } int main() { int result; int test[] = {0,1,8,16,23,35,47,59}; result = InterpolationSearch(test,sizeof(test)/sizeof(test[0]),23); printf("%d\n",result); system("pause"); return 0; }