剑指offer读书笔记之不修改数组找出数组中重复的数字

public class  {
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
        System.out.println(findDuplicate(arr));
    }
    private static int findDuplicate(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int start = 1;
        int end = arr.length - 1;
        while (end >= start) {
            int middle = ((end - start) >> 1) + start;
            int count = countRange(arr, start, middle);
            if (end == start) {
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            if (count > (middle - start + 1)) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }
    private static int countRange(int[] arr, int start, int end) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= start && arr[i] <= end) {
                ++count;
            }
        }
        return count;
    }
}