如何修改插值搜索算法，未找到目标时返回可定位最近值的索引

我帮你调整了插值搜索的实现，现在当目标值不在有序数组中时，会返回数组里最接近它的元素索引。先看完整的代码实现：

public static int InterSearch(double[] array, double data)
{
    if (array == null || array.Length == 0)
        return -1; // 处理空数组情况
    
    int size = array.Length;
    int lo = 0;
    int hi = size - 1;
    int mid = -1;

    while (lo <= hi)
    {
        // 避免除以0：当lo和hi位置元素相等时，直接跳出循环处理最近值
        if (array[hi] == array[lo])
        {
            if (array[lo] == data)
                return lo;
            break;
        }

        // 计算插值搜索的mid索引
        mid = lo + ((hi - lo) * (int)(data - array[lo])) / (int)(array[hi] - array[lo]);

        // 防止mid越界（比如data远大于/小于数组元素时）
        mid = Math.Max(lo, Math.Min(mid, hi));

        if (array[mid] == data)
        {
            return mid; // 找到目标，直接返回索引
        }
        else if (array[mid] < data)
        {
            lo = mid + 1; // 目标在右半区，调整左边界
        }
        else
        {
            hi = mid - 1; // 目标在左半区，调整右边界
        }
    }

    // 循环结束，未找到目标，开始寻找最近值
    // 边界情况1：目标比所有元素都小
    if (hi < 0)
        return 0;
    // 边界情况2：目标比所有元素都大
    if (lo >= size)
        return size - 1;
    
    // 比较hi和lo位置的元素哪个更接近data
    double diffHi = Math.Abs(data - array[hi]);
    double diffLo = Math.Abs(data - array[lo]);
    
    // 差值相等时默认返回左边的hi索引，可根据需求调整
    return diffHi <= diffLo ? hi : lo;
}

关键修改说明 #

• 空数组处理：先判断数组是否为空，避免后续逻辑出现索引越界错误
• 除以0防护：当array[hi]和array[lo]相等时（比如数组所有元素相同），直接跳出循环进入最近值判断，防止计算mid时出现除以0的异常
• mid越界防护：用Math.Max和Math.Min确保mid始终在lo和hi的范围内，避免因data极端值导致的索引越界
• 未找到时的最近值判断：
  • 如果hi < 0，说明目标值比数组中最小元素还小，返回第一个元素索引
  • 如果lo >= size，说明目标值比数组中最大元素还大，返回最后一个元素索引
  • 否则比较array[hi]和array[lo]与目标值的差值，返回差值更小的那个索引；若差值相等，默认返回左边的hi索引

注意：这个实现的前提是数组必须是升序排列的，插值搜索本身只适用于有序数组哦。

内容的提问来源于stack exchange，提问作者Craig