二分查找 vs 插值查找：算法比较及 Java 代码实现

二分查找和插值查找是两种常见的查找算法，它们的主要区别在于查找的中间位置的计算方式不同。

二分查找：
- 中间位置的计算方式：使用简单的平均值计算中间位置，即 mid = (low + high) / 2。
- 适用范围：适用于有序数组。
- 实现代码：

public int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // 表示未找到
}

插值查找：
- 中间位置的计算方式：根据查找值的大小，使用插值公式计算中间位置，即 mid = low + (target - array[low]) / (array[high] - array[low]) * (high - low)。
- 适用范围：适用于有序数组，且分布比较均匀的情况。
- 实现代码：

public int interpolationSearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high && target >= array[low] && target <= array[high]) {
        int mid = low + (target - array[low]) / (array[high] - array[low]) * (high - low);
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // 表示未找到
}

注意：以上代码都是基于有序数组进行查找，如果是无序数组，需要先进行排序操作。另外，插值查找在某些情况下可能会比较快，但对于分布不均匀的情况，二分查找可能更合适。