数据结构-查找-插值查找法

╰+攻爆jí腚メ 2023-10-04 16:28 10阅读 0赞

#### 插值查找法 ####

插值查找法又叫做插补查找法，是二分查找法的改进版。它是按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用插值法是假设数据平均分布在数组中，而每一项的差距相当接近或有一定的距离比例。插值法的公式为：

Mid = low + ((key - data\[low\]) / (data\[high\] - data\[low\])) \* (high - low)

其中Key是要查找的键值，data\[high\],data\[low\]是剩余待查找记录中的最大值和最小值，假设数据项为n，其插值查找法的步骤如下：

*  将记录从小到大的顺序给于1，2，3，…，n的编号
 *  令low=1，high=n
 *  当low<high时，重复执行步骤4和步骤5
 *  令Mid=low+(key - data\[low\]) / (data\[high\] - data\[low\]) \* (high - low)
 *  若key<keyMId且high≠Mid-1，则令high=Mid-1
 *  若key=keyMid，表示成功查找到键值的位置
 *  若key>keyMid且low≠Mid+1，则令low=Mid+1

**插值查找法的分析**

1.  一般而言，插值查找法优于顺序查找法，数据的分布越平均查找速度越快，甚至可能第一次就找到数据。此法的时间复杂度取决于数据分布的情况，平均而言优于O(logn)
2.  使用差值查找法数据需要先经过排序

**设计一个程序使用插值查找法**

#使用快排对数组进行排序
    import random
    
    
    def quickSort(d,size,lf,rg):
        if lf < rg:     #排序数列的左边和右边
            lf_idx = lf + 1
            while d[lf_idx] < d[lf]:
                if lf_idx >= size:
                    break
                lf_idx += 1
            rg_idx = rg
            while d[rg_idx] > d[lf]:
                rg_idx -= 1
            while lf_idx < rg_idx:
                d[lf_idx],d[rg_idx] = d[rg_idx],d[lf_idx]
                lf_idx += 1
                while d[lf_idx] < d[lf]:
                    lf_idx += 1
                rg_idx -= 1
                while d[rg_idx] > d[lf]:
                    rg_idx -= 1
            d[lf],d[rg_idx] = d[rg_idx],d[lf]
            #分割前后接着递归排序
            quickSort(d,size,lf,rg_idx - 1)
            quickSort(d,size,rg_idx + 1,rg)
    #插值查找法
    def interSearch(data,val):
        low = 0
        high = 49
        while low < high and val != -1:
            mid = low + int((val - data[low]) / (data[high] - data[low]) * (high - low))
            if val == data[mid]:
                return mid
            elif val < data[mid]:
                high = mid - 1
            elif val > data[mid]:
                low = mid + 1
        return -1
    
    def main():
        val = 1
        data = [0] * 50
        for i in range(50):
            data[i] = random.randint(1,150)
        #为数组排序
        quickSort(data,len(data),0,len(data)-1)
        #数组内容
        for i in range(5):
            for j in range(10):
                print('%2d [%3d] '%(i*10+j+1,data[i*10+j]),end='')
            print()
        #二分法查找
        while True:
            num = 0
            val = int(input("请输入查找值(1-150),输入-1结束："))
            if val == -1:
                break
            num = interSearch(data,val)
            if num == -1:
                print("=============没有找到[%2d]============="%val)
            else:
                print('在第%2d的位置找到了%3d'%(num+1,data[num]))
    
    if __name__ == '__main__':
        main()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FrTXLWm9-1625207345677)(/home/lnnu/.config/Typora/typora-user-images/image-20210702142654466.png)\]

**注意：**

**int((val - data\[low\]) / (data\[high\] - data\[low\]) \* (high - low))**

和**int((val - data\[low\]) \* (high - low)/ (data\[high\] - data\[low\]) )**

这两个按照数学的计算来说没有任何问题，但是放在代码里是可能会出现完全不一样的结果，仔细琢磨

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210702142719669.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70