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

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

插值查找的工作原理：

确定查找范围：首先确定待查找关键字的上下界，即数组的起始位置和结束位置。
计算插值位置：根据当前的上下界，使用插值公式计算出一个预测位置 pos。
```
pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
```
其中 key 是要查找的关键字，arr 是有序数组，low 和 high 分别是当前查找区间的下界和上界。
比较并调整：将数组中的 pos 位置的值与关键字进行比较。
- 如果 arr[pos] == key，则查找成功。
- 如果 arr[pos] < key，则新的查找区间的下界 low 更新为 pos + 1。
- 如果 arr[pos] > key，则新的查找区间的上界 high 更新为 pos - 1。
重复步骤 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 + 1if (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] + "]");}
}