比方说，我们有一个未排序的数组，其中的数字从0到n（n = 2 ^ k-1，k是整数）除外。我的目标是找到丢失的号码。
我知道XOR方法或sum方法。但是，我必须使用分而治之的策略，这与数组的中位数有关。
我的想法是找到数组的中位数，然后将数组递归分为2个数组。 （一个数字将小于或等于中位数，另一个数字将大于或等于中位数。类似于二进制搜索）。
但是，我认为这没有用。您有什么建议？
caoxh1975 回答：使用除数，征服和中位数从未排序的数组中找到缺失的数字 分治法 Python实现：
这是另一个主意。
分治法
- 让缺失的数字
m为n / 2。 - 计算小于
m的数字。 - 如果计数小于
m- 然后，我们知道丢失的数字小于
m。 - 否则，丢失的数字大于或等于
m。
- 然后，我们知道丢失的数字小于
继续执行此操作，直到找到丢失的号码为止。
Python实现：
def missingNumber(nums):
lo,hi = 0,len(nums)
while lo < hi:
m = (lo + hi + 1) // 2
smaller = sum(x < m for x in nums)
if smaller < m:
hi = m - 1
else:
lo = m
return lo
您可以将数组分为2个数组，一个数组的值较小，另一个数组的值大于中位数。您可以根据第一句的假设来检查这两个数组应有多少个元素。
然后，数组之一必须比假定的要小1。因此，您可以在那里搜索。
这样，您的退出条件将类似于该数组应包含x与x之间的所有元素（因此只是x），但它为空。因此，x是缺少的元素。