Special Array With X Elements Greater Than or Equal X

求一个数字x, 数组中的数字大于等于x的数字个数正好是x. 如果有x, 返回x, 否则返回 -1.

这个题首先看肯定是O(n^2)能解决的, 就是暴力破解. 然后这题一看x是对大小有考量, 肯定用binary search能优化, 用二叉肯定要先找边界, 所以看题知道边界是[0, n]. 然后再看用哪种二叉搜索, 这题因为答案唯一(题中给了, 不给的话自己prove很难, 我估计着狗家这题肯定是没告诉你答案必然唯一的, 如果想不到答案必然唯一, 这题很难在短时间写出来.), 剩下的就直接就写出来了..

class Solution {
    public int specialArray(int[] nums) { 
        Arrays.sort(nums);
        int start = 0;
        int end = nums.length; 
        while(start <= end) {
            int mid = start + (end - start) / 2;
            int c = count(nums, mid);
            if(c == mid){ 
                return mid;
            } else if(c > mid) {
                start = mid  + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
    private int count(int[] nums, int i) {
        int c = 0;
        for(int n : nums) {
            if(n >= i)
                c++;
        }
        return c;
    }
}