C语言实现数组中的插值查找并返回下标

插值查找是一种利用比较次数较少的查找算法，其基本思想是根据查找值与查找表中最大值和最小值的比例，利用类似于二分查找的方法查找目标值。下面是C语言实现数组中的插值查找并返回下标的代码：

#include <stdio.h>
#include <stdlib.h>

// 插值查找
int interpolation_search(int arr[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high && x >= arr[low] && x <= arr[high]) {
        int pos = low + ((x - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        if (arr[pos] == x)
            return pos;
        else if (arr[pos] < x)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int index = interpolation_search(arr, n, x);
    if (index != -1)
        printf("元素 %d 在数组中的下标是 %d\n", x, index);
    else
        printf("元素 %d 不在数组中\n", x);
    return 0;
}

在上面的代码中，函数`interpolation_search`接收一个整型数组`arr`、数组长度`n`和要查找的元素`x`，返回`x`在`arr`中的下标。如果`x`不在`arr`中，则返回-1。函数中使用了while循环来进行查找，根据查找值`x`与查找表中最大值和最小值的比例，计算出中间位置的下标`pos`，并与`x`进行比较，根据比较结果更新查找范围。最终，如果找到了`x`，则返回其下标，否则返回-1。在`main`函数中，我们声明一个整型数组`arr`和要查找的元素`x`，调用`interpolation_search`函数进行查找，并输出查找结果。