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.

Solution: run time complexity is in O(log n)
取中间值mid，比较citations[mid]和length-mid做比较，如果前者大，则right移到mid之前，反之right移到mid之后，终止条件是left>right，最后返回length-left.

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