题目描述：
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1: 输入: [1,3,4,2,2]
输出: 2
示例 2: 输入: [3,1,3,4,2]
输出: 3
说明： 不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
思路分析：
关键：这道题的关键是对要定位的“数”做二分，而不是对数组的索引做二分。要定位的“数”根据题意在 1 和 n 之间，每一次二分都可以将搜索区间缩小一半。
以 [1, 2, 2, 3, 4, 5, 6, 7] 为例，一共有 8 个数，每个数都在 1 和 7 之间。1 和 7 的中位数是 4，遍历整个数组，统计小于 4 的整数的个数，至多应该为 3 个，如果超过 3 个就说明重复的数存在于区间 [1,4) （注意：左闭右开）中；否则，重复的数存在于区间 [4,7]（注意：左右都是闭）中。这里小于 4 的整数有 4 个（它们是 1, 2, 2, 3），因此砍掉右半区间，连中位数也砍掉。以此类推，最后区间越来越小，直到变成 1 个整数，这个整数就是我们要找的重复的数。
代码实现：
class Solution {
public static int findDuplicate(int[] nums) {
int len = nums.length;
int left = 1;
int right = len - 1;
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 0; i < len; i++) {
if (nums[i] <=mid) {
count++;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
时间复杂度：O(nlogn)
空间复杂度：O(1)
