题设
    给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

    示例 1:

    输入: [1,3,4,2,2]
    输出: 2
    示例 2:

    输入: [3,1,3,4,2]
    输出: 3
    说明：

    不能更改原数组（假设数组是只读的）。
    只能使用额外的 O(1) 的空间。
    时间复杂度小于 O(n2) 。
    数组中只有一个重复的数字，但它可能不止重复出现一次

    解法—二分查找
    分析
    通常我们使用二分查找时都是在有序数组中做以下方面的搜索操作

    • 查找值等于某个元素的下标 (无重复元素)
    • 查找第一个等于给定值的元素
    • 查找最后一个等于给定值的元素
    • 查找第一个大于等于给定值的元素
    • 查找最后一个小于等于给定值的元素

    不论是什么情况，算法都是在首尾指针大小关系未发生变化前缩小搜索的区间范围，并在首尾指针大小关系变化后找返回结果。
    题设中要求不能更改原数组的值，同时只能使用额外的 O(1) 的空间，这意味着不能对元素组做排序处理。
    但是对于 n+1 个数，每个数的取值范围在[1,n] 范围内且仅有一个数重复出现 的题设条件，如果统计数组中小于等于 某个值 i 的元素个数，可以得到一个有序的数组，以输入[1,3,4,2,2,5,2]为例 | 元素值 i | 1 | 2 | 3 | 4 | 5 | 6 | | —- | —- | —- | —- | —- | —- | —- | | <= i 个数 | 1 | 4 | 5 | 6 | 7 | 7 |

    记cnt(i) 为数组中小于等于元素 i 的元素个数，则有：

    • 若 [1,i] 的范围内的元素没有缺失时且重复元素也不在[1,i]范围内时 cnt(i) == i
    • 若 重复元素在[1,i] 的范围内时, cnt(i) > i；这里可以从剩余元素来考虑, 剩余元素在[i+1,n] 的范围内取值且不能重复所以剩余元素最多只能有 n-i个 从而推出 cnt(i) = n+1 - cnt(i) <= n-i ,进一步有 cnt(i) >= i+1
    • 若重复元素不在 [1,i] 范围内时，cnt(i) <= i

    可以看到当且仅当重复元素落在区间[1,i]范围内时， cnt(i) > i，因此：
    我们需要找的是重复的元素，因此在统计出 cnt(i) 的值之后，可以通过二分查找的方式去锁定重复元素所在的区间，然后并更新mid为重复元素，这里在未二分查找循环未结束前保存的mid并不一定为数组中的重复元素，但是通过后续的 cnt(i) > i 时的更新可以将区间缩小为1，这时 左右指针指向同一个值，这个值(mid) 就是要找的重复元素。

    实现

    1.     public int findDuplicate(int[] nums) {
    2.         int len = nums.length;
    3.         int l = 0 , r = len - 1, mid , ans = 0;
    4.         while(l <= r){
    5.             mid = l + ((r-l) >>> 1);
    6.             int cnt = 0;
    7.             for(int i = 0 ; i < len ; i++){
    8.                 if(nums[i] <= mid){
    9.                     cnt++;
    10.                 }
    11.             }
    12.             if(cnt <= mid){
    13.                 l = mid + 1;
    14.             }else{
    15.                 r = mid - 1;
    16.                 ans = mid;
    17.             }
    18.         }
    19.         return ans;
    20.     }