02_不修改数组找出重复数字

要求：

在一个长度为n+1的数组里的所有数字都在1到n的范围内。 数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组；

思路：

数组长度为n+1，而数字只从1到n，说明必定有重复数字。可以由二分查找法拓展：把1--n的数字从中间数字m分成两部分，若前一半1--m的数字数目超过m个，说明重复数字在前一半区间，否则，在后半区间m+1~n。每次在区间中都一分为二，知道找到重复数字。

public int getDuplication(final int[] numbers, int length){
        if(numbers == null||length<=0){
            return -1;
        }
        int start = 1;
        int end = length-1;
        while(end>=start){
//            int middle = ((end+start)/2);    // 相当于下式
            int middle = ((end-start)>>1)+start;  // 右移1位相当于处于2
            System.out.println("+++"+middle);   // 输出中间索引值
            int count = countRange(numbers,length,start,middle);  // 计算前半段的数目个数
            if(end == start){
                if(count>1){
                    return start;
                }else{
                    break;
                }
            }
            if(count>=(middle-start+1)){  // 若前一半1--m的数字数目超过m个，说明重复数字在前一半区间
                end = middle;
            }else{  // 否则在后半区
                start = middle+1;
            }

        }
        return -1;
    }
    // 计算numbers[]中start到end的数字的个数,例如[1,2,3,4,3]中属于1到4的数目为5个。
    public int countRange(int[] numbers,int length,int start,int end){
        if(numbers == null){
            return 0;
        }
        int count = 0;
        for(int i=0;i<length;i++){
            if(numbers[i]>= start && numbers[i]<=end){
                count++;
            }
        }
        return count;
    }

// 测试
public static void main(String[] args) {
        int[] arr= {2,3,5,4,3,2,6,7};
        L02_getDuplication gd = new L02_getDuplication();
        int d = gd.getDuplication(arr, arr.length);
        System.out.println(d);
    }

时间复杂度O(nlogn)，其中（while循环为O(logn)，coutRange()函数为O(n)）