Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

二分，我們去統(tǒng)計數組中小于等于mid出現的個數，顯然，當出現的個數小于或者相等mid時，左側是合法的，重復出現在右半部分，當小于等于mid的數出現的次數大于mid的值時，說明重復出現在左半部分。
小于是可以出現的，只要這個數出現的次數足夠多，導致從1-mid的數中有至少一個數沒有出現。

class Solution {
    public int findDuplicate(int[] nums) {
        int lo = 1 ;
        int hi = nums.length-1;
        int count = 0;
        int pos =0;
        while(lo<=hi)
        {
            count=0;
            int mid = lo+(hi-lo)/2;
            for(int i = 0 ;i<nums.length;i++)
            {
                if(nums[i]<=mid)
                    count++;
            }
            // <= when contains no duplicate ;
            // > when contains duplicate ;
            if(count<=mid)
                lo=mid+1;
            else if(count>mid)
            {
               
                hi=mid-1;
            } 
      
        }
        return lo;
    }
   
}