在一个长度为 n+1 的数组李所有的数字都在 1~n 的范围内。请找出数字中任意一个重复的数字，但不能修改输入的数组。
解：
时间复杂度为 O(n*logn)，空间复杂度为 O(1)。
但该算法不能保证找出所有重复的数字。如 {2, 3, 5, 4, 3, 2, 6, 7} 中找不到重复的数字 2。
// 验证数组输入的正确性
public static boolean validateArray(int[] array) {
if (array == null || 0 == array.length)
return false;
for (int i = 0; i < array.length; i++) {
if (array[i] < 1 || array[i] > array.length)
return false;
}
return true;
}
public static int getDuplication(int[] array) {
if (validateArray(array)) {
// 数组内的所有数字都在 1 到 array.length - 1 的范围内
int start = 1;
int end = array.length - 1;
// 二分法，当 start == end 时退出循环，此时 start 的值就是出现重复的值
while (start != end) {
// 求中间的数字
int middle = (end + start) >> 1;
// 记录从 start 到 middle 的数字在数组中出现的次数
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] >= start && array[i] <= middle)
count++;
}
// 与“n 中有 n + 1 个数字，则必有一个数字是重复的”同理
if (count > middle - start + 1)
end = middle;
else
start = middle + 1;
}
return start;
}
return -1;
}
