287. Find the Duplicate Number

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.

二分，我们去统计数组中小于等于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;
    }
   
}