_{算法 4th}

# 二分查找
def rank(key, array): 
    """二分查找，查找key是否在數(shù)組array中    數(shù)組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()
    # 測試數(shù)據(jù)目錄
    data_path = 'D:\Codes\python\Algorithms4th\\algs4-data\\' 
    # 讀取測試數(shù)據(jù)，各100萬條數(shù)據(jù)
    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迭代需要時(shí)間就比較長
    print('所用時(shí)間：%r秒' %(end-start))