1139.md

题目：随机匹配。编写一个使用 BinarySearch 的程序，它从命令行接受一个整形参数 T，并会分别针对 N=10的三次方、10的四次方、10的五次方和10的六次方，将以下实验运行 T 遍：生成两个大小为 N 的随机6位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格，对于每个 N，给出 T 次实验中该数量的平均值。

解答：题目也不难，输入 T 次，在 N 的不同情况下分别重复 T 次查找，计算查找的次数和平均值。

def test1139(self, t):
    def binarySearch(k, a):
        lo = 0
        hi = max([len(a)-1, 0])
        while lo <= hi:
            mid = lo + (hi-lo)//2
            if a[mid] < k:
                lo = mid+1
            elif a[mid] > k:
                hi = mid-1
            else:
                return mid
        return -1
    
    def proArr(n):
        res = []
        for i in range(0, n):
            res.append(random.randint(100000, 1000000))
        return res

    time = [1000, 10000, 100000, 1000000]
    for n in range(0, len(time)):
        cnt = 0
        for ti in range(0, t):
            a1 = proArr(time[n])
            a2 = proArr(time[n])
            for i in range(0, time[n]):
                idx = binarySearch(a1[i], a2)
                if idx >= 0:
                    cnt += 1
        avg = cnt / t
        print(f'N:{time[n]}, total time:{t}, count:{cnt}, avg:{avg}')

电脑运行的比较慢，只尝试了T=12的情况：

N:1000, total time:12, count:0, avg:0.0
N:10000, total time:12, count:2, avg:0.16666666666666666
N:100000, total time:12, count:23, avg:1.9166666666666667
N:1000000, total time:12, count:297, avg:24.75