[中等]287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

分析：难度在于下面的要求，不能更改原数组，只能使用O(1)空间，时间复杂度小于O(n2) 。如果没有这些要求，有以下解法，（1）n次循环该数组，记录1-n每个数字出现的次数，最坏情况时间复杂度 O(n2)，且使用了O(N)空间；（2）对数组进行排序，选择一种时间复杂度小于O(n2)的排序算法，然后循环该有序数组，查找其中重复数字；（3）使用额外O(N)空间，循环该数组，记录每个数字出现的次数，时间复杂度O(N)。
但是在该要求的限制下，必须考虑其他方法。
这里使用一种二分法的方式来查找重复数字。首先确定一个中间值，记(n+1)//2，左边界1，右边界n，循环该数组，找小于等于该中间值和大于该中间值的数字数量，如果小于等于该中间值的数量比中间值大，则说明重复数字在左侧。将右边界赋值为原中间值，根据左右边界重新计算一个中间值，再对数组进行一次循环，按照上述方法，直到左右边界差值为1，说明只剩下两个数字了，再分别计算这两个数字的个数，找到重复数字。
这种方法的时间复杂度为O(NLOGN)，因为二分法的时间复杂度为2^k=N，k=logn，每次划分都要循环一遍数组n，所以是O(NLOGN)。