昨天搞了下二分查找，今天看看它的升级版：插值查找。

插值查找核心思想是尽量将中间值取的更靠近要查找的目标以减少运算次数，而非像二分法那样盲目的取中间值，即：

{{mid=left+ \tfrac{(dst-arr[left])}{(arr[right]-arr[left])}*(right-left)}}

它的缺点与二分法类似,理想情况下时间复杂度为：

{{O(log_2 N)}}

int insert_search(int arr[], int dst, int left, int right)
{
    int mid = left + (dst - (arr[left]) / (arr[right] - arr[left])) * (right - left);
    if (arr[mid] == dst)
        return mid;
    if (arr[mid] > dst)
        return insert_search(arr, dst, left, mid - 1);
    if (arr[mid] < dst)
        return insert_search(arr, dst, mid + 1, right);
}