---

前言

查找算法是一种用于在数据集合中查找特定元素的算法。在计算机科学中，查找算法通常被用于在数组、链表、树等数据结构中查找目标元素的位置或者判断目标元素是否存在。
查找算法的目标是在尽可能短的时间内找到目标元素，以提高程序的效率和性能。常见的查找算法包括但不限于二分查找、哈希表查找、线性查找、二叉查找树等。

一、查找算法预备知识

查找算法分类

1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）
需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。

二、插值查找

插值查找是一种在有序数组中查找目标元素的查找算法，它是对二分查找的改进，特别适用于数据分布均匀的情况。插值查找的原理是根据目标元素与数组边界值的比例来估计目标元素的位置，从而快速缩小查找范围。基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。

    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high ) {
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
            if (arr[pos] == target) {
                return pos; // 返回目标元素的索引位置
            } else if (arr[pos] < target) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }

        return -1; // 如果未找到目标元素，返回-1
    }


    public static void test3() {
        int[] arr = {12, 11, 15, 50, 7, 65, 3, 99};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        int result = interpolationSearch(arr, 15);
        if (result != -1) {
            System.out.println("目标元素 " + 15 + " 在数组中的索引位置为: " + result);
        } else {
            System.out.println("目标元素 " + 15 + " 未找到");
        }
    }

输出：

对比二分查找：

  int mid = (left + right) >>> 1;

 int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

其实就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

三、总结

3.1 查找性能

最坏情况下，时间复杂度为O(n)，当数据分布不均匀时，插值查找可能退化为线性查找。
平均情况下，时间复杂度为O(log(log n))，比二分查找的O(log n)稍优。

3.2 适用场景

数据分布均匀：插值查找适用于数据分布均匀的情况，可以快速定位目标元素。
连续性数据：适用于连续性数据，例如数字等。
中等规模数据：适用于中等规模的有序数组，可以提供较高的查找效率。