內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

8.4插值查找算法

插值查找原理介紹：

1.????? 插值查找算法類似于二分查找，不同的是插值查找每次從自適應(yīng)mid處開始查找。

2.????? 將折半查找中的求mid索引的公式,low表示左邊索引left,high表示右邊索引right, key就是前面我們講的findVal

1.????? int mid = low + (high - low) * (key - arr[low])/ (arr[high] - arr[low]);/*插值索引*/對應(yīng)前面的代碼公式:

int mid = left +(right - left) * (findVal - arr[left])/ (arr[right]- arr[left])

2.????? 舉例說明插值查找算法1-100的數(shù)組

8.4.1插值查找應(yīng)用案例

請對一個有序數(shù)組進(jìn)行插值查找{1,8,10,89,1000,1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并且求出下標(biāo)，如果沒有就提示"沒有這個數(shù)"。

代碼實(shí)現(xiàn)

8.4.2插值查找的注意事項

1.????? 對于數(shù)據(jù)量較大，關(guān)鍵字分布比較均勻的查找表來說，采用插值查找，速度較快

2.????? 關(guān)鍵字分布不均勻的情況下，該方法不一定比折半查找要好