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);}
}

插值查找虽然在特定情况下效率很高，但它依赖于数据的均匀分布。以下是三道可能出现在大厂面试中的与插值查找相关的编程题目，以及相应的Java源码实现。

题目 1：有序数组中的查找

描述：
给定一个有序整数数组，写一个方法来查找一个目标值是否存在于数组中。

示例：

输入: nums = [4, 5, 6, 7, 7, 8, 8], target = 6
输出: true

Java 源码：

public class SearchInSortedArray {public boolean search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return true;}if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}public static void main(String[] args) {SearchInSortedArray solution = new SearchInSortedArray();int[] nums = {4, 5, 6, 7, 7, 8, 8};int target = 6;boolean result = solution.search(nums, target);System.out.println("Target " + target + " found: " + result);}
}

题目 2：有序矩阵中的查找

描述：
给定一个 m x n 的有序整数矩阵（每行从左向右递增，每列从上到下递增），请写出一个方法来查找目标值是否存在于矩阵中。

示例：

输入:
matrix = [[1,   4,  7, 11, 15],[2,   5,  8, 12, 19],[3,   6,  9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]
]
target = 5
输出: true

Java 源码：

public class SearchInSortedMatrix {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int midValue = matrix[mid / n][mid % n];if (target == midValue) {return true;}if (target < midValue) {right = mid - 1;} else {left = mid + 1;}}return false;}public static void main(String[] args) {SearchInSortedMatrix solution = new SearchInSortedMatrix();int[][] matrix = {{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};int target = 5;boolean result = solution.searchMatrix(matrix, target);System.out.println("Target " + target + " found in matrix: " + result);}
}

题目 3：找出有序数组中缺失的数字

描述：
给定一个有序整数数组，其中有些数字是重复的，有些数字可能缺失，找出并返回缺失的最小正整数。

示例：

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

Java 源码：

public class FindMissingNumber {public int findMissing(int[] nums) {int n = nums.length;int sum = (n + 1) * n / 2; // 计算理想情况下的和int actualSum = 0;for (int num : nums) {actualSum += num;}return sum - actualSum;}public static void main(String[] args) {FindMissingNumber solution = new FindMissingNumber();int[] nums = {2, 3, 4, 6, 7, 9, 12};int missingNumber = solution.findMissing(nums);System.out.println("Missing number: " + missingNumber);}
}