#include<iostream>
using namespace std;
int search(const int*, int, int);
int main()
{
int arr[6] = {1,2,3,4,10,20};
int find = search(arr, 6, 10);
if(find == -1)
cout << "没有找到!" << endl;
else
cout << arr[find] << endl;
return 0;
}
int search(const int* arr, int size, int key)
{
int tou, wei, zhong;
tou = 0;
wei = size - 1;
while(tou <= wei)
{
zhong = tou + (wei - tou) * (key - arr[tou]) / (arr[wei] - arr[tou]); //拉法朗日算法
if(key == arr[zhong])
{
return zhong;
}
else if(key < arr[zhong])
{
wei = zhong - 1;
}
else
tou = zhong + 1;
}
return -1;
} 拉格朗日插值查找法
原文：http://blog.csdn.net/linukey/article/details/44957575
