假设我们有一个未排序的数组，其中的数字从0到n（n = 2 ^ k-1，k是一个整数）除外。我的目标是找到丢失的号码。
我知道XOR方法或sum方法。但是，我必须使用分而治之的策略，这与数组的中位数有关。
我的想法是找到数组的中位数，然后将其递归分成2个数组。 （一个将具有小于或等于中位数的数字，另一个将具有大于或等于中位数的数字。类似于二进制搜索）。
但是，我认为这没有用。您建议进行哪些更改？
您可以将数组分为2个数组，一个数组的值较小，另一个数组的值大于中位数。您可以根据第一句话的假设，检查这两个数组应有多少个元素。然后，其中一个数组必须比假定的要小1。因此，您可以在那里搜索。这样，您的退出条件将类似于该数组应包含x与x之间的所有元素（因此只是x），但它为空。因此，x是缺少的元素。