1 算法题 ：使用插值查找算法在有序数组中查找指定元素
1.1 题目含义
使用插值查找算法在有序数组中查找指定元素。插值查找是介于线性查找和二分查找之间的一种查找算法，它是基于二分查找的改进算法。插值查找的核心思想在于根据待查找元素的值在有序数组中的位置，利用数学公式计算出该元素在数组中的大致位置，从而缩小查找范围，提高查找效率。
1.2 示例
示例 1:
输入：
- nums = [1, 3, 4, 7, 10, 12, 13, 16, 18, 20]
- target = 7
输出： 3
说明： 7 存在于 nums 中，且其索引为 3。
示例 2:
输入：
- nums = [1, 3, 4, 7, 10, 12, 13, 16, 18, 20]
- target = 25
输出： -1
说明： 25 不存在于 nums 中，返回 -1。
示例 3:
输入：
- nums = []
- target = 0
输出： -1
说明： nums 为空，0 不存在于 nums 中，返回 -1。
2 解题思路
2.1 循环遍历实现
（1）初始化参数：
- 确定有序数组 arr 和待查找元素 target。
- 获取数组的长度 n。
- 设置数组的起始索引 low 为 0，结束索引 high 为 n - 1。
（2）检查边界情况：
- 如果 target 小于 arr[low] 或大于 arr[high]，则 target 不在数组中，直接返回 -1。
（3）计算插值位置：
- 使用插值公式计算 target 在数组中的大致位置 pos。插值公式通常如下：
pos = low + ((target - arr[low]) * (high - low) / (arr[high] - arr[low]))
- 确保 pos 是一个合法的索引值，即它应在 low 和 high 之间。如果 pos 不合法，则将其限制在合法范围内。
（4）缩小查找范围（比较 arr[pos] 与 target）：
- 如果它们相等，返回 pos，因为找到了目标元素。
- 如果 target 小于 arr[pos]，则新的结束索引 high 更新为 pos - 1。
- 如果 target 大于 arr[pos]，则新的起始索引 low 更新为 pos + 1。
（5）循环查找：
- 使用一个循环来重复上述步骤，直到找到目标元素或查找范围为空。
- 在每次循环中，重新计算插值位置 pos 并根据比较结果更新查找范围。
（6）返回结果：
- 如果在循环结束前找到了 target，则返回其索引。
- 如果循环结束后仍未找到 target（即 low 大于 high），则返回 -1，表示 target 不在数组中。
2.2 递归实现
（1）初始化参数：
- 确定有序数组 arr 和待查找元素 target。
- 获取数组的长度 n。
- 设置数组的起始索引 low 为 0，结束索引 high 为 n - 1。
（2）检查边界情况：
- 如果 target 小于 arr[low] 或大于 arr[high]，则 target 不在数组中，直接返回 -1。
（3）递归函数定义：
- 定义一个递归函数 interpolationSearchRecursive，该函数接受当前查找范围的起始索引 low、结束索引 high、目标值 target 和数组 arr 作为参数。
（4）计算插值位置：
- 使用插值公式计算 target 在数组中的大致位置 pos。插值公式通常如下：
pos = low + ((target - arr[low]) * (high - low) / (arr[high] - arr[low]))
- 确保 pos 是一个合法的索引值，即它应在 low 和 high 之间。如果 pos 不合法，则将其限制在合法范围内。
（5）递归调用（比较 arr[pos] 与 target）：
- 如果它们相等，返回 pos，因为找到了目标元素。
- 如果 target 小于 arr[pos]，则在数组的左半部分（low 到 pos - 1）继续递归查找。
- 如果 target 大于 arr[pos]，则在数组的右半部分（pos + 1 到 high）继续递归查找。
- 递归调用 interpolationSearchRecursive 函数，传入更新后的查找范围和目标值。
（6）递归终止条件：
- 找到了目标元素，返回其索引。
- 查找范围为空（即 low 大于 high），表示目标元素不在数组中，返回 -1。
（7）返回结果：
- 根据递归函数返回的结果，输出目标元素是否存在于数组中以及它的索引。
3 算法实现代码
3.1 循环遍历实现
如下为算法实现代码：
#include <iostream>
#include <string>
#include <vector>
class Solution
{
public:
int interpolationSearch(std::vector<int>& nums, int target) {
int n = arr.size();
if (n <= 0) {
return -1; // 空数组，返回-1
}
int low = 0, high = n - 1;
// 检查边界情况
if (target < arr[low] || target > arr[high]) {
return -1; // 目标值不在数组范围内
}
while (low <= high && arr[low] <= target && arr[high] >= target) {
// 计算插值位置
int pos = low + static_cast<int>(
((double)(high - low) / (arr[high] - arr[low]) * (target - arr[low]));
// 检查pos是否越界
if (pos < low || pos > high) {
pos = (pos < low) ? low : high;
}
// 比较arr[pos]与目标值
if (arr[pos] == target) {
return pos; // 找到目标值，返回其索引
}
// 根据比较结果更新查找范围
if (arr[pos] < target) {
low = pos + 1;
} else {
high = pos - 1;
}
}
// 没有找到目标值
return -1;
}
};
这段代码首先检查数组的边界情况，然后进入一个循环，在循环中计算插值位置，并根据比较结果更新查找范围。循环会一直执行，直到找到目标元素或确定目标元素不在数组中。最后，返回找到的元素的索引或-1表示未找到。
调用上面的算法，并得到输出：
int main()
{
Solution s;
std::vector<int> arr = { 1, 3, 4, 7, 10, 12, 13, 16, 18, 20 };
int target = 7;
int index = s.interpolationSearch(arr, target);
if (index != -1) {
std::cout << "Element " << target << " found at index: " << index << std::endl;
}
else {
std::cout << "Element " << target << " not found in the array." << std::endl;
}
return 0;
}
上面代码的输出为：
Element 7 found at index: 3
3.2 递归实现
如下为算法实现代码：
#include <iostream>
#include <string>
#include <vector>
class Solution
{
public:
int interpolationSearch(std::vector<int>& nums, int target) {
return interpolationSearchRecursive(nums, target, 0, nums.size() - 1);
}
private:
int interpolationSearchRecursive(const std::vector<int>& nums, int target, int low, int high) {
// 检查边界情况
if (low > high || target < nums[low] || target > nums[high]) {
return -1; // 目标值不在数组范围内
}
if (low == high) {
return (nums[low] == target) ? low : -1; // 如果low和high相等，检查是否找到目标值
}
// 计算插值位置
int pos = low + static_cast<int>(
((double)(high - low) / (nums[high] - nums[low]) * (target - nums[low])));
// 确保pos是合法索引
pos = (pos < low) ? low : (pos > high) ? high : pos;
// 比较nums[pos]与目标值
if (nums[pos] == target) {
return pos; // 找到目标值，返回其索引
}
else if (nums[pos] < target) {
return interpolationSearchRecursive(nums, target, pos + 1, high); // 在右半部分递归查找
}
else {
return interpolationSearchRecursive(nums, target, low, pos - 1); // 在左半部分递归查找
}
}
};
在这段代码中，interpolationSearchRecursive 成员函数函数是递归查找的主体，它接受数组 nums、目标值 target、当前查找范围的起始索引 low 和结束索引 high 作为参数。函数首先检查边界情况，然后计算插值位置，并递归地在左半部分或右半部分查找，直到找到目标值或确定目标值不在数组中。interpolationSearch 函数是外部调用接口，它初始化了查找范围并调用了递归函数。
4 测试用例
以下是针对上面算法的测试用例，基本覆盖了各种情况：
（1）基础测试用例
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 9
输出：4
说明：目标值 9 存在于数组中，位于索引 4 的位置。
（2）目标值不存在于数组中
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 2
输出：-1
说明：目标值 2 不存在于数组中。
（3）目标值位于数组开头
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 -1
输出：0
说明：目标值 -1 位于数组的开头，即索引 0 的位置。
（4）目标值位于数组末尾
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 12
输出：5
说明：目标值 12 位于数组的末尾，即索引 5 的位置。
（5）目标值位于数组中间
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 3
输出：2
说明：目标值 3 位于数组的中间位置，即索引 2 的位置。
（6）空数组
输入：数组 []，目标值 9
输出：-1
说明：空数组不包含任何元素，因此无法找到目标值。
（7）数组只有一个元素
输入：数组 [9]，目标值 9
输出：0
说明：数组只有一个元素，且该元素就是目标值，位于索引 0 的位置。
（8）数组中存在多个相同的目标值
输入：数组 [1, 2, 3, 3, 4, 5]，目标值 3
输出：2 或 3
说明：数组中存在多个目标值 3，返回任意一个目标值的索引都是正确的。这里可以返回 2 或 3。
