//插值查找  ------  有序数组  
int InsertValueSearch(vector<int>arr, int left, int right, int val)
{
    //cout << "插值查找被调用" << endl;
    if (left > right||val<arr[0]||val>arr[arr.size()-1])
    {
        return - 1;
    }
    int mid = left + (right - left)*(val - arr[left]) / (arr[right] - arr[left]);
    int midVal = arr[mid];
    if (arr[mid] > val)
    {
         return InsertValueSearch(arr, left, mid - 1, val);
    }
    else if (arr[mid] < val)
    {
        return InsertValueSearch(arr, mid + 1, right, val);
    }
    else
    {
        return mid;
    }
}

int main()
{
    vector<int>arr;
    for (int i = 0; i < 100; i++)
    {
        arr.push_back(i + 1);
    }
    int n=InsertValueSearch(arr, 0, arr.size() - 1, 98);
    cout << n << endl;

    system("pause");
    return 0;
}