287. Find the Duplicate Number

287. Find the Duplicate Number.java

public class Solution {
    public int findDuplicate(int[] nums) {
        
        int low = 1, high = nums.length - 1;
        
        while (low <= high) {
            int mid = (int) (low + (high - low) * 0.5);
            int cnt = 0;
            for (int a : nums) {
                if (a <= mid) ++cnt;
            }
            if (cnt <= mid) low = mid + 1;
            else high = mid - 1;
        }
        
        return low;
    }
}