H-Index II

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

Hint:

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

Tips:

The basic idea of this solution is to use binary search to find the minimum index such that

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

Just binary search, each time check citations[mid]

1. case 1: citations[mid] == len-mid, then it means there are citations[mid] papers that have at least citations[mid] citations.
2. case 2: citations[mid] > len-mid, then it means there are citations[mid] papers that have more than citations[mid] citations, so we should continue searching in the left half
3. case 3: citations[mid] < len-mid, we should continue searching in the right side

After iteration, it is guaranteed that right+1 is the one we need to find (i.e. len-(right+1) papars have at least len-(righ+1) citations)

Code:

public class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        if (len == 0) {
            return 0;
        }
        int left = 0;
        int mid;
        int right = len - 1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (citations[mid] >= (len - mid)){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return len - (right + 1);
    }
}