275. H Index II

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

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

解题思路： The basic idea of this solution is to use binary search to find the minimum index such that

citations[index] >= length(citations) - index

After finding this index, the answer is length(citations) - index.

采用binary search，时间复杂度为O(logn)。 注意点是对于[0,0,...,0]特例的处理。

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0) return 0;
        int len = citations.length;
        int start = 0, end = len - 1;
        while(start < end) {
            int mid = start + (end - start) / 2;
            if(citations[mid] < (len - mid)) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return citations[start] >= (len - start) ? len - start : 0;
    }
}