算法 4th
# 二分查找
def rank(key, array):
"""二分查找，查找key是否在数组array中 数组array必须有序 """
lo = 0
hi = len(array)-1
while lo <= hi:
mid = lo + int((hi - lo) / 2)
# print(mid)
if key < array[mid]:
hi = mid - 1
elif: key > array[mid]:
lo = mid + 1
else:
return mid
return -1
# in 方法迭代查找
def fin(key, array):
if key not in array:
print(key)
if __name__ == '__main__':
import time
start = time.time()
# 测试数据目录
data_path = 'D:\Codes\python\Algorithms4th\\algs4-data\\'
# 读取测试数据，各100万条数据
whitefilelarge = open(data_path + 'largeW.txt', 'r')
targetfilelarge = open(data_path + 'largeT.txt', 'r')
whitelist = []
for line in whitefilelarge:
whitelist.append(int(line))
# 白名单排序
whitelist.sort()
for key in targetfilelarge:
# 二分法
if rank(int(key), whitelist) < 0:
print(key)
# # in方法迭代，可以对比测试下
# fin(key, whitelist)
whitefile.close()
targetfile.close()
end = time.time()
# 二分查找大概需要10秒多，for in迭代需要时间就比较长
print('所用时间：%r秒' %(end-start))
