004.【查找算法】插补查找算法

1. 插补查找算法

插补查找算法又称为插值查找，它是折半查找算法的改进版。插补算法是按照数据的分布，利用公式预测键值所在的位置，快速缩小键值所在序列的范围，慢慢逼近，直到查找到数据为止。由此可以看出，插补查找算法比折半查找算法的取值范围更小，因此它的速度要比折半法查找快，这就是插补查找算法的优点。

键值的索引计算公式：

middle = left + (target-data[left])/(data[right]-data[left])*(right-left)
1

• middle：所求的边界索引
• target：键值（目标数据）
• left：最左侧数据的索引
• right：最右侧数据的索引
• data[left]：最左侧数据值
• data[right]：最右侧数据值

2. 利用插补查找用户输入的数据

用户可以随意输入一组数据，例如输入一组数据：34、53、57、68、72、81、89、93、99。在这组数据中用插补查找法分别查找数据 57、53、93、89、100，显示每次查找的过程。

def insret_seach(data,num):                                                 # 自定义插补查找函数
    low=0                                                                   # 定义变量表示最低位
    high=8                                                                  # 义变量表示最高位
    print("正在查找......")
    while low<=high and num!=-1:                                            # 循环判断低位小于等于高位且键值不等于-1
        mid=low+int((num-data[low])*(high-low)/(data[high]-data[low]))      # 用插补查找核心 计算出边界位置
        if num==data[mid]:                                                  # 如果键值等于边界值
            return mid                                                      # 返回边界位置
        elif num<data[mid]:                                                 # 如果键值小于边界值
            print('%c介于位置%d[%c]和边界值%d[%c]之间，找左半边'%(num,low+1,data[low],mid+1,data[mid]))    # 输出在左半边查找
            high=mid-1                                                      # 最高位等于边界位置减1
        elif num>data[mid]:                                                 # 如果键值大于边界值
            print('%c介于边界值位置%d[%c]和%d[%c]之间，找右半边'%(num,mid+1,data[mid],high+1,data[high]))  # 输出在右半边查找
            low=mid+1                                                       # 最低位等于边界位置加1
    return -1                                                               # 自定义函数到此结束



data = [34,53,57,68,72,81,89,93,99]                                         # 定义数列            
print("数据内容是：")
for i in range(9):                                                          # 遍历行
                                                         					# 遍历列
    print(' %d[%d]' % (i+1,data[i]),end='')         						# 输出数列

print()
while True:                                                                 # 循环查找
    number = 0                                                              # 定义变量用来存储查找结果
    num = int(input("请输入查找键值，输入-1退出程序："))
    if num == -1:                                                           # 判断键值是否是-1
        break                                                               # 若为-1，跳出循环
    number = insret_seach(data, num)                                        # 调用自定义的查找函数——search()函数
    if number == -1:                                                        # 判断查找结果是否是-1
        print('没有找到[%d]' % num)
    else:
        print('在%d个位置找到[%d]' % (number + 1, data[number]))              # 若不为-1，提示查找位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36