#include<stdio.h>
#define MAX 11
int binary_search(int *, int, int, int);
int binary_search(int *arr, int low, int high, int key)
{
int mid, count;
count = 0;
while (low <= high) {
// 折半查找法
mid = (low + high)/2;
printf("折半查找法: 第%d次查找, low=%d, mid=%d, high=%d\n", ++count, low, mid, high);
// 插值查找法(书中未加1.0 *这一步，实际测试如果不加的话达不到效果)
//mid = low + 1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low);
//printf("插值查找法: 第%d次查找, low=%d, mid=%d, high=%d\n", ++count, low, mid, high);
if (key < arr[mid])
// high赋值为mid前1个，表示下一次循环查询左半部分
high = mid - 1;
else if (key > arr[mid])
// low赋值为mid后1个，表示下一次循环查询右半部分
low = mid + 1;
else
return mid;
}
return 0;
}
int main(void)
{
int arr[MAX] = {0, 1, 3, 5, 6, 11, 22, 25, 27, 30, 35};
printf("search 30 range 1,10, result: %d\n", binary_search(arr, 1, 10, 30));
printf("search 3 range 1,10, result: %d\n", binary_search(arr, 1, 10, 3));
printf("search 30 range 1,5, result: %d\n", binary_search(arr, 1, 5, 30));
return 0;
}
output(分别去掉注释测试)
[root@8be225462e66 c]# gcc binary_search.c && ./a.out
插值查找法: 第1次查找, low=1, mid=8, high=10
插值查找法: 第2次查找, low=9, mid=9, high=10
search 30 range 1,10, result: 9
插值查找法: 第1次查找, low=1, mid=1, high=10
插值查找法: 第2次查找, low=2, mid=2, high=10
search 3 range 1,10, result: 2
插值查找法: 第1次查找, low=1, mid=12, high=5
插值查找法: 第2次查找, low=1, mid=-289, high=11
search 30 range 1,5, result: 0
[root@8be225462e66 c]# gcc binary_search.c && ./a.out
折半查找法: 第1次查找, low=1, mid=5, high=10
折半查找法: 第2次查找, low=6, mid=8, high=10
折半查找法: 第3次查找, low=9, mid=9, high=10
search 30 range 1,10, result: 9
折半查找法: 第1次查找, low=1, mid=5, high=10
折半查找法: 第2次查找, low=1, mid=2, high=4
search 3 range 1,10, result: 2
折半查找法: 第1次查找, low=1, mid=3, high=5
折半查找法: 第2次查找, low=4, mid=4, high=5
折半查找法: 第3次查找, low=5, mid=5, high=5
search 30 range 1,5, result: 0
[root@8be225462e66 c]#原文：https://blog.51cto.com/sndapk/2726674