基于二分查找的插值查找公式推导过程的

Question

最近在看插值查找，对于他的公式都是基于二分推导出来的
二分：mid = 1/2（left+right） = left+1/2(right-left)
插值查找：
设定比值为k,查找值为key k=(key - a[right])(a[left]-a[right])
根据二分公式left+1/2(right-left)，将1/2替换为k推导而出：mid = left+k(right-left) 其结果简化可得mid = kright+(l-k)left
但如果是根据二分公式：mid = 1/2（left+right），将1/2替换成k却推导而出：mid = k(left+right) 简化可得mid = kright+kleft
两者都是将1/2替换为k,最终推导出的公式不一样，那么如何确定他的正确性呢？又或者插值公式的正确推导应该是什么样子的呢？

Answer 1

mid = left+k(right-left) 其结果简化可得mid = kright+k(l-left) 这一步简化没看懂呀；
我理解 mid = left+k(right-left) 推导得 mid = left + kright - kleft ,提取公因式，简化得到 mid =kright +left(1-k)，不知道对不对。
二分查找是插值查找特例把，K换成1/2后两者貌似是相同的

Answer 2

• 请看👉 ：二分查找与插入排序的结合使用