補間検索(補間検索)ほかんけんさく(ほかんけんさく)

これは二分と似た検索アルゴリズムですが、分布が均一な大きな配列に対しては、補間検索が一度に検索できる場合があります.
どうしてこんなに早くできるの`?ネット上にこのアルゴリズムについての説明がないので、説明しましょう.
まず、この検索方式はシーケンステーブルのみに対して行うことができ、もう一つはシーケンステーブルの特徴を理解し、シーケンステーブルに値があるかどうかを検索する.この場合、シーケンステーブルのいずれかの要素を比較することができ、Aに値がtの要素があるかどうかを検索する場合は、a[i]とtで比較する.(a[i]は、シーケンステーブルの任意の要素であってもよい.)もしa[i]=tならば、iはtの位置で、a[i]>tならば、tはきっとa[i],a[i+1]にいないことを説明します....a[n-1], a[n]... つまり今はa[1].a[i-1]検索を行えばよい.
よく理解して、もし上の理解ができないならば、補間は探して理解しにくいです..
次にlowとhighで検索範囲を保存し、最初はlow=0、hight=n-1でした.iをlowからhighまでの相対位置とする.例えば、i=0、low=0の場合、tとa[i+low]を比較する、すなわち、tがa[0]と等しいか否かを判断する.
iがどこにいるかを確認します.
順序テーブルの分布が均一であると仮定すると、次の方程式があります.
　　(t - a[low]) : (i + low) = (a[high] - a[low]) : (high - low)
　　i = (t - a[low]) * (high - low)/(a[high] - a[low]) + low;
差は少ないでしょう...
私の言語表現能力は限られていますが、まだよく理解していない場合は、コードを見てみましょう.

/* a        ,, size a   , t        */
int search(int a[], int size, int t)
{
	int low = 0, high = size - 1;
	int pos;
	while(low <= high){
		pos = (t - a[low])/(a[high] - a[low])*(high - low) + low;
		if(a[pos] == t){
			return pos;
		}
		if(a[pos] > t){
			high = pos - 1;
		}else{
			low = pos + 1;
		}
	}
	return -1;
}