Leetcode: H-Index II

ollow 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.

Understand the problem:
Since the problem asks for a O(log n) solution, we can think of using a binary search. 

Code (Java):

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

        if (citations[lo] >= len - lo) {
            return len - lo;
        }
        
        if (citations[hi] >= len - hi) {
            return len - hi;
        }
        
        return 0;
    }
}