有序查找之：折半查找和插值查找(C语言)

#includestdio.h#define MAX 11int 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 + ...

#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]#