Java插值查找知识点（含面试大厂题和源码）

插值查找（Interpolation Search）是一种改进的二分查找算法，适用于数据分布均匀的有序数组。插值查找的基本思想是，根据要查找的关键字与数组的最大值和最小值之间的比例，预测关键字可能存在的位置，从而跳过一些不可能包含关键字的区间，以此来减少查找所需的比较次数。

插值查找的工作原理：

1. 确定查找范围：首先确定待查找关键字的上下界，即数组的起始位置和结束位置。
2. 计算插值位置：根据当前的上下界，使用插值公式计算出一个预测位置 pos。

   pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
   

   其中 key 是要查找的关键字，arr 是有序数组，low 和 high 分别是当前查找区间的下界和上界。
3. 比较并调整：将数组中的 pos 位置的值与关键字进行比较。
   • 如果 arr[pos] == key，则查找成功。
   • 如果 arr[pos] < key，则新的查找区间的下界 low 更新为 pos + 1。
   • 如果 arr[pos] > key，则新的查找区间的上界 high 更新为 pos - 1。
4. 重复步骤 2 和 3：直到找到关键字或者查找范围无效（即 low > high）。

插值查找的优缺点：

优点：

• 对于均匀分布的数据，插值查找的平均查找效率可以达到 O(log log n)。
• 插值查找可以快速跳过不可能包含关键字的区间，减少比较次数。

缺点：

• 插值查找的性能依赖于数据的分布情况，对于非均匀分布的数据，其性能可能下降到 O(n)。
• 插值查找需要对数据进行额外的处理（如计算插值位置），这可能增加算法的复杂性。

插值查找的Java实现：

public class InterpolationSearch {
    public int interpolationSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && key >= arr[low] && key <= arr[high]) {
            if (low == high) {
                if (arr[low] == key) {
                    return low;
                }
                return -1;
            }

            // 计算插值位置
            int pos = low + Math.round(((double) (high - low) / (arr[high] - arr[low])) * (key - arr[low]));

            if (arr[pos] == key) {
                return pos;
            } else if (arr[pos] < key) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }

        return -1; // 如果没有找到，返回-1
    }

    public static void main(String[] args) {
        InterpolationSearch search = new InterpolationSearch();
        int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
        int key = 18;
        int index = search.interpolationSearch(arr, key);
        System.out.println("Index of " + key + " is: " + index);
    }
}

在面试中，了解插值查找的原理和实现是非常重要的，尤其是当面试官询问如何处理有序数据集的查找问题时。插值查找是二分查找的一种变体，适用于数据分布均匀的场景，但在数据分布不均匀的情况下，其性能可能不如二分查找。

题目 1：有序数组中的众数

描述：
给定一个大小为 n 的有序数组，找到数组中的众数。众数是指在数组中出现次数超过 ⌊ n/2 ⌋ 的元素。

示例：

输入: [2, 3, 3, 4, 4, 4, 6, 6, 7, 8, 9]
输出: 4

Java 源码：

public class MajorityElement {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) {
                count++;
            } else if (count == 1) {
                candidate = nums[i];
                count = 1;
            } else {
                count--;
            }
        }
        // 验证众数
        int majorityCount = 0;
        for (int num : nums) {
            if (num == candidate) {
                majorityCount++;
            }
        }
        return (majorityCount > nums.length / 2) ? candidate : -1;
    }

    public static void main(String[] args) {
        MajorityElement solution = new MajorityElement();
        int[] nums = {2, 3, 3, 4, 4, 4, 6, 6, 7, 8, 9};
        int result = solution.majorityElement(nums);
        System.out.println("The majority element is: " + result);
    }
}

题目 2：有序数组中的第 K 个缺失的正数

描述：
给定一个有序数组，其中包含了从 1 到 n 的部分整数，找出数组中第 k 个缺失的正数。

示例：

输入: [2, 3, 4, 7, 9], k = 4
输出: 6

Java 源码：

public class KthMissingPositive {
    public int findKthPositive(int[] arr, int k) {
        int n = arr.length;
        int maxElement = 0;
        for (int num : arr) {
            if (num > maxElement) {
                maxElement = num;
            }
        }
        // 计算缺失的正数数量
        int missingCount = maxElement - 1 - n;
        // 如果 k 小于缺失的数量，直接返回 k + 1
        if (k <= missingCount) {
            return k + 1;
        }
        // 否则，找到第一个大于 (k - missingCount - 1) 的元素
        for (int i = 0; i < n; i++) {
            if (arr[i] > (k - missingCount - 1)) {
                return (k - missingCount - 1) + (k - i);
            }
        }
        return (k - missingCount - 1) + n;
    }

    public static void main(String[] args) {
        KthMissingPositive solution = new KthMissingPositive();
        int[] arr = {2, 3, 4, 7, 9};
        int k = 4;
        int result = solution.findKthPositive(arr, k);
        System.out.println("The kth missing positive number is: " + result);
    }
}

题目 3：有序数组中的两个和为特定值的元素

描述：
给定一个有序整数数组，找到两个数，使得它们的和等于特定值。如果存在这样的两个数，返回它们的数组索引，否则返回 [-1, -1]。

示例：

输入: [2, 3, 4, 6, 7, 9, 11], target = 11
输出: [1, 5]

Java 源码：

public class TwoSumII {
    public int[] twoSumII(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        TwoSumII solution = new TwoSumII();
        int[] numbers = {2, 3, 4, 6, 7, 9, 11};
        int target = 11;
        int[] result = solution.twoSumII(numbers, target);
        System.out.println("The indices of the two numbers are: [" + result[0] + ", " + result[1] + "]");
    }
}

这些题目和源码展示了插值查找在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！