python算法9.18——插值排序

# 对二分查找的改进，也是对有序表进行查询
# 基本原理：
# mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])

import random
Range = 10
Length = 5
flag = 0
pos = -1

list = random.sample(range(Range),Length)
goal = random.randint(0,Range)
# list =  [0, 1, 4, 5, 7]
# goal = 10

# 冒泡排序处理
for i in range(Length-1):                   #控制循环次数
    for j in range(Length-i-1):             #控制每次循环内容
        if list[j] > list[j + 1]:
            list[j + 1], list[j] = list[j], list[j + 1]
print('search ',goal,', in list:',list)

min = 0
max = Length - 1
mid = min + int((max - min)*(goal - list[min])/(list[max] - list[min]))

if goal>list[max]:
    pass
else:
    while min<max:
        mid = min + int((max - min) * (goal - list[min]) / (list[max] - list[min]))
        if list[mid] == goal:
            flag = 1
            pos = mid
            break
        elif list[mid] > goal:
            max = mid - 1
        elif list[mid] < goal:
            min = mid + 1

if flag:
    print('find in ',pos+1,'th place')
else:
    print('not found')