一、代码
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define MAXSIZE 20
typedef int Status
;
Status
binarySearch(int arr
[],int arrLenght
,int wantSearchElement
);
int main(int argc
, char *argv
[]) {
int data
[MAXSIZE
],size
,i
,wantSearch
,result
;
printf("请输入初始化数组大小(1-%d):",MAXSIZE
);
scanf("%d",&size
);
printf("请输入数组元素(空格隔开):");
for(i
=1;i
<=size
;i
++)
{
if(scanf("%d",&data
[i
])==0)
{
printf("输入错误\n");
fflush(stdin);
return ERROR
;
}
}
printf("请输入你要查找的内容:");
if(scanf("%d",&wantSearch
)==0)
{
printf("输入错误\n");
fflush(stdin);
return ERROR
;
}
if((result
=binarySearch(data
,size
,wantSearch
))==ERROR
)
{
printf("你要查找的元素不在数组中\n");
return ERROR
;
}
printf("元素在数组中%d位置\n",result
);
return 0;
}
Status
binarySearch(int arr
[],int arrLenght
,int wantSearchElement
)
{
int low
=1,hight
=arrLenght
,mid
;
while(hight
>=low
)
{
mid
=low
+(hight
-low
)*(wantSearchElement
-arr
[low
])/(arr
[hight
]-arr
[low
]);
if(arr
[mid
]>wantSearchElement
)
{
hight
=mid
-1;
}
else if(arr
[mid
]<wantSearchElement
)
{
low
=mid
+1;
}else
{
return mid
;
}
}
return ERROR
;
}
二、代码中重要的函数或语句
mid
=low
+(hight
-low
)*(wantSearchElement
-arr
[low
])/(arr
[hight
]-arr
[low
]);
这条是核心语句。插值查找的核心就在于插值计算公式mid=low+[(key-arr[low])/(arr[hight]-arr[low])]*(hight-low)
三、运行截图
插值查找用在比较均匀分布的表中效率比折半查找好得多，但是用在极端不均匀的数据表中，不一定合适。
