不修改数组找出重复的数字

题目：

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

解答：

 1 public class Solution {
 2 
 3     public static void main(String[] args) {
 4         int arr = {2,3,5,4,3,2,6,7};
 5         System.out.println(getDuplication(arr, arr.length))
 6     }
 7 
 8     public static int getDuplication(int[] arr, int length) {
 9         if(arr == null || length <= 0) {
10             return -1;
11         }
12 
13         // 1-n
14         int start = 1;
15         int end = length-1;
16 
17         while(start >= end) {
18             int mid = (end-start)>>1 + start;
19 
20             int count = countRange(arr, length, start, mid);
21 
22             if(end == start) {
23                 if(count > 1) {
24                     return start;
25                 } else {
26                     break;
27                 }
28             }
29 
30             if(count > (mid-start+1)) {
31                 end = mid;
32             } else {
33                 start = mid + 1;
34             }
35         }
36 
37         return -1;
38 
39     }
40 
41     private static int countRange(int[] arr, int length, int start, int mid) {
42         if(arr == null) {
43             return 0;
44         }
45 
46         int count = 0;
47         for(int i = 0; i < length; i++) {
48             //
49             if(arr[i] >= start && arr[i] <= mid) {
50                 count++;
51             }
52         }
53 
54         return count;
55     }
56 }