title: 插值查找
comments: true
date: 2018-04-24 20:47:15
categories:

  • ACM
  • 查找算法

插值查找

插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,
其核心就在于查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式
$$pos = low+\frac{val-num[low]}{num[high]-num[low]}(high-low) $$

需要注意的是:

  1. $val > num[low]$
  2. $val > num[high]$

这两种情况要判一下下

时间复杂度

  1. 这个O(loglogN)的复杂度是平均期望复杂度,而不是最坏情况复杂度。
  2. 需要假设数据在某个范围内均匀分布。

代码

int Search(int val) {
    int l = 0, r = 100;
    int ans = -1;
    while (l <= r) {
        if (val < num[l] || val - num[l] > r - l) break;
        int m = l + (val - num[l]) * (r - l) / (a[r] - a[l]);
        if (ok(m)) {
            ans = m;
            l = m + 1;
        } else
            r = m - 1;
    }
    if (ans == -1)
        cout << "Find nothing" << endl;
    return ans;
}
最后修改:2020 年 07 月 30 日 10 : 17 PM