数组中重复的数（题目二）

《剑指offer》面试题3：题目二：不修改数组找出重复的数字。

题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内。所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为7的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

思路：数组中的数都在1 ~ n范围内，把从1 ~ n的数从中间的数字m分为2部分，左部分为1 ~ m，右部分为m+1 ~ n，如果1 ~ m这m个数在数组中的总个数超过m，则这一半的区间里一定包含重复的数；否则，另一半区间里一定包含重复的数。继续把包含重复的数的区间一分为二，知道找到一个重复的数。

代码如下：

public int getDuplication(int[] numbers,int length) {
    if (null == numbers || length <= 0) {
        return -1;
    }
    for (int i = 0;i < length;i++) {
        if (numbers[i] < 1 || numbers[i] > n) {
            return -1;
        }
    }
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        int count = 0;
        for (int i = 0;i < length;i++) {
            if (numbers[i] >= left && numbers[i] <= right) {
                count++;
            }
        }
        if (count > right - left + 1) {
            right = middle;
        } else {
            left = middle;
        }
        if (left == right) {
            if (count > 1) {
                return left;
            }
        }
    }
    return -1;
}