在实际应用中，有序向量内的元素不仅单调排列，而且往往还服从某

[问答题]

在实际应用中，有序向量内的元素不仅单调排列，而且往往还服从某种概率分布。若能利用这一性质，则可以更快地完成查询。

以查阅英文字典为例，单词"Data"应大致位于前1/5和1/4之间，而"Structure"则应大致位于后1/5和1/4之间。对元素的分布规律掌握得越准确，这种加速效果也就越加可观。

此类方法的原理大同小异，无非是利用向量元素的分布规律，根据目标数值，通过插值估计出其大致所对应的秩，从而迅速缩小搜索范围，故称作插值查找（interpolation search）。

a）若有序向量中的元素均独立且等概率地取自某一数值区间，试证明它们应大致按线性规律分布；

b) 针对此类有序向量，如何通过插值来估计待查找元素的秩？试给出具体的计算公式；

c)试证明：对于长度为 n 的此类向量，插值查找的期望运行时间为 $\sigma$ (loglogn)；

牛客902898874号

private int insertSearch(int []nums, int left, int right, int value) {
    if(left > right || value < nums[0] || value > nums[nums.length-1]) {
        return -1;
    }
    int mid = left + (right-left)*(value-nums[left]/(nums[right]-nums[right]);)
    int midValue = nums[mid];
    
    if(value > midValue) {
        return binarySearch(nums, mid+1, right, value);
    } else (value < minValue) {
        return binarySearch(nums, left, mind-1, value);
    } else {
        return mid;
    }
}

发表于 2020-10-14 23:33:34 回复(0)