查找算法-插值查找法（Interpolation Search）
目录
查找算法-插值查找法（Interpolation Search）
1、说明
2、算法分析
3、C++代码
查找算法-插值查找法（Interpolation Search）
1、说明
插值查找法又称为插补查找法，是二分查找法的改进版。它是按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用插值查找法是假设数据平均分布在数组中，而每一项数据的差距相当接近或有一定的距离比例。插值查找法的公式为：
其中，key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大值和最小值。
2、算法分析
- 一般而言，插值查找法优于顺序查找法，如果数据的分布越平均，查找速度就越快，甚至可能第一次就找到数据。插值查找法的时间复杂度取决于数据分布的情况，平均而言优于
。
- 使用插值查找法的数据需要先经过排序。
3、C++代码
#include<iostream>
using namespace std;void SetData(int* Data, int Size) {for (int i = 0; i < Size; i++) {Data[i] = rand() % 150 + 1;}
}void Sort(int* Data, int Size) {for (int i = 0; i < Size; i++) {for (int j = i + 1; j < Size; j++) {if (Data[i] > Data[j]) {int temp = Data[i];Data[i] = Data[j];Data[j] = temp;}}}
}void Print(int* Data, int Size) {for (int i = 0; i < Size / 10; i++) {for (int j = 0; j < 10; j++) {cout << Data[i * 10 + j] << "\t";}cout << endl;}
}int InterpolationSearch(int* Data, int Size, int Value) {int low = 0;int high = Size - 1;while (low <= high && Value != -1) {int mid = low+((Value-Data[low])/(Data[high]-Data[low]))*(high - low);if (Value < Data[mid]) {high = mid - 1;}else if (Value > Data[mid]) {low = mid + 1;}elsereturn mid;}return -1;
}int main() {int Size = 80;int* Data = new int[Size] {0};SetData(Data, Size);Sort(Data, Size);cout << "原始数据：" << endl;Print(Data, Size);cout << "---------------------" << endl;int num = 0;cout << "请输入想要查找的数据：";cin >> num;int index = -1;index = InterpolationSearch(Data, Size, num);if (index != -1)cout << "查找的数据在数据库的第[ " << index + 1 << " ]位" << endl;elsecout << "在数据库中没有找到该数据" << endl;return 0;
}输出结果
