每日算法（2）——不修改数组找出重复的数字

在一个长度为 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;
    }