275. H-Index II (Medium)

Follow up for H-Index: What if thecitationsarray is sorted in ascending order? Could you optimize your algorithm?

[0, 1, 4, 5, 6]

Solution 1: Binary Search O(log n); O(1)

   /**
     * Think about the definition of h index: h papers that have >= h citations.
     * If pick an index in the citations array, mid.
     * The # of papers have >= h citations is: array length - mid.
     * If citations[mid] = length - mid, return mid.
     * If citations[mid] > length - mid, papers not enough, mid should be smaller.
     * If citations[mid] < length - mid, too many papers, mid should be larger.
     */
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }

        int n = citations.length;
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (citations[mid] == n - mid) { //引用次数=大于等于该引用次数的论文数
                return n - mid;
            }
            if (citations[mid] > n - mid) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return n - start; //最后肯定是start=end-1，因为最后一次while循环中start=end=mid，要么end-1，要么start+1。
    }