插值查找

插值查找是根据数据的实际分布情况计算可能的位置，适合于数据分布均匀的情况。当预期的关键字值为均匀分布时，插值查找比折半查找更有效率；否则插值查找的效率会很差。

记住mid的求解公式就可以了，这很简单。

代码

#include<iostream>
using namespace std;
int SearchInter(int num[],int key,int number) {
    int low = 0, high = number - 1, mid;
    while (low <= high) {
        mid = (key - num[low])*(high - low) / (num[high] - num[low]);
        if (num[mid] == key) return mid+1;
        else if (num[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
void main() {
    int num[12] = { 1,3,5,7,9,11,13,15,17,19,21,23 };
    int key = 11;
    int index = SearchInter(num, key, 12);
    cout << key << "的位置是" << index << endl;
    system("pause");
}

---

本文总阅读量次 本站访客数人次