algorithm - 关于数组中缺少元素的问题

Question

我在麻省理工大学的书籍介绍算法第二版中遇到以下问题

问题如下

An array A[1 . . n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0 . . n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the j th bit of A[i],” which takes constant time.

Show that if we use only this operation, we can still determine the missing integer in O(n) time

请帮忙

Answer 1

调用您丢失的号码 M。

您可以根据 A[i] 的最低有效位是 1 还是 0 将数组分成两部分。两部分中较小的一个(称为 P_1 ) 的大小最多为 (n-1)/2 个元素，它会告诉您 M 的最低有效位是 1 还是 0 .

现在考虑 P_1 元素的第 2 位。同样，这部分可以分成两部分，两部分中较小的部分 (P_2) 告诉您该位应该是 1 还是 0。

继续(P_3，P_4，...)直到你弄清楚所有的位是什么。

您可以证明这是 O(n)，因为您本质上是在查看 n + n/2 + n/4 + ...你的数组，这个总和小于 2n。