查找 --- 插值查找

插值查找(Interpolation Search)是二分查找的优化，只是针对1/2的改进

int Interpolation_Search(int *a, int n, int key) {
    int low, height, mid;
    low = 0;
    height = n;
    int k_whiler = 0;
    while (low <= height) {
        k_whiler++;
        printf("第 %d 次查找 \n",k_whiler);
        mid = low + (key - a[low])/(a[height]-a[low]) * (height - low);
        if(key < a[mid]) {
            height = mid - 1;
        }else if (key > a[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return 0;
}

​