如何计算插值搜索（Interpolation Search）查找数组元素的耗时

核心实现思路 #

• 统计耗时的逻辑非常简单：在搜索算法触发前记录起始时间，算法执行完成后立刻记录结束时间，二者差值就是搜索过程的耗时
• 纳秒级精度统计使用System.nanoTime()，适合这类执行速度极快的搜索算法统计；如果只需要毫秒级精度可以替换为System.currentTimeMillis()
• 若要得到更稳定的测试结果，可多次执行搜索取平均耗时，抵消单次运行时系统调度、JIT即时编译带来的误差

修改后的完整代码 #

import java.util.*;
class GFG {
    // 如果x在arr[0..n-1]中存在则返回对应下标，否则返回-1
    public static int interpolationSearch(int arr[], int lo,
                                          int hi, int x)
    {
        int pos;
        // 数组有序的前提下，元素存在的话必然在边界值定义的区间内
        if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
            // 基于均匀分布假设计算探测位置
            pos = lo
                  + (((hi - lo) / (arr[hi] - arr[lo]))
                     * (x - arr[lo]));
            // 找到目标元素
            if (arr[pos] == x)
                return pos;
            // x更大，目标在右子数组
            if (arr[pos] < x)
                return interpolationSearch(arr, pos + 1, hi,
                                           x);
            // x更小，目标在左子数组
            if (arr[pos] > x)
                return interpolationSearch(arr, lo, pos - 1,
                                           x);
        }
        return -1;
    }
    // 主方法
    public static void main(String[] args)
    {
        // 待搜索的数组
        int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                      22, 23, 24, 33, 35, 42, 47 };
        int n = arr.length;
        // 待搜索的目标元素
        int x = 18;
        
        // 耗时统计开始
        long startTime = System.nanoTime();
        int index = interpolationSearch(arr, 0, n - 1, x);
        long endTime = System.nanoTime();
        // 计算耗时
        long costNanos = endTime - startTime;
        double costMillis = costNanos / 1_000_000.0;

        // 输出结果
        if (index != -1)
            System.out.println("元素找到，下标为 " + index);
        else
            System.out.println("元素未找到");
        System.out.printf("搜索耗时：%d 纳秒，%.6f 毫秒%n", costNanos, costMillis);
    }
}

注意事项 #

• 统计区间不要包含无关逻辑（比如结果打印、数组初始化），否则会影响耗时统计的准确性
• 如果需要做专业的性能基准测试，建议使用JMH（Java微基准测试框架），可以规避JIT、垃圾回收等因素带来的统计误差

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