在前面我們了解了二分查找嘁字，就是把一個(gè)集合的元素一分為二夫椭，用中間值和目標(biāo)查找值相比較掸掸，直到要查找的值和中間值相等，則表示查找成功蹭秋，反之表示不成功扰付。為什么這里會(huì)再次提到二分查找呢？事實(shí)上仁讨，插值查找是二分查找的升級(jí)版羽莺。
用一個(gè)很簡單的例子就可以把插值查找解釋的很清楚。在字典里面找”boy”這個(gè)單詞時(shí)洞豁，我們肯定不會(huì)從第一頁開始找盐固，而是從首字母為b的位置開始查找，然后再找到第二個(gè)字母在字母表中的位置丈挟，找到對(duì)應(yīng)的位置后刁卜，重復(fù)這個(gè)過程，這樣就可以快速的找到目標(biāo)單詞曙咽。
接下來就介紹一下插值查找吧蛔趴。
我們知道的的二分查找有一個(gè)必要的前提，必須是有序的數(shù)組才可以進(jìn)行二分查找例朱，同樣插值查找也只能用于一個(gè)呈線性增長的有序數(shù)組中孝情。
首先我們?cè)跀?shù)組中找到左邊索引low和右邊的索引high，目標(biāo)查找值key
在二分查找中mid表示數(shù)組的中間值洒嗤，而插值查找中mid表示一個(gè)自適應(yīng)處箫荡，插值查找每次是從自適應(yīng)mid處開始查找，mid的計(jì)算方式為：low + (key – arr[low]) / (arr[high] – arr[low]) * (high - low)渔隶；在這里mid表示的就是目標(biāo)值key在序列總的所占比羔挡。
源碼：
int func(int arr[], int len, int key)
{
? ? ? int low,high,mid;
? ? ? low = 0;
? ? ? high = len-1;
? int h = (key-arr[low])/(arr[high]-arr[low]);
? ? ? while(low <= high)
? ? ? {
? ? ? ? ? mid = h * (high - low);
? ? ? ? ? if(key < arr[mid])
? ? ? ? ? {
? ? ? ? ? ? ? high = mid - 1;
? ? ? ? ? }
? ? ? ? ? else if(key > arr[mid])
? ? ? ? ? {
? ? ? ? ? ? low = mid + 1;
? ? ? ? ? }
? ? ? ? ? else
? ? ? ? ? {
? ? ? ? ? ? ? return mid;
? ? ? ? ? }
? ? ? }
? ? return -1;
? }
文章來源：學(xué)到牛牛 www.xuedaon.com
