如果两个人A和B有两个大的布尔列表，如何找到列表中的第一个不匹配，两个人之间的数据传输最少？

Question

假设列表中的人A = [T，T，F，T，F ...]并列出人B = [T，T，F，T，T ...]，那么我们需要说索引4是列表中的第一个不匹配位置。 列表中的条目数量可能非常大（约5000万）。如何在两个人之间传输的数据量（字节数）最少的情况下有效地执行此搜索？

Answer 1

您可以使用Merkle树结构并找到O(log n)传输中的不匹配。对于256位散列函数（例如SHA256），您可以按256个元素的一部分拆分数组。这部分将是Merkle树的叶子。